Link to this headingRSA

  • Works on Small messages that are less than the keylength
  • For 128-bit security level, a 3072-bit key is required.
  • Partially Homomorphic through multiplication. Enc(m_1) * Enc(m_2) == Enc(m_1 * m_2)

https://hackernoon.com/how-does-rsa-work-f44918df914b
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
https://crypto.stackexchange.com/questions/11117/simple-digital-signature-example-with-number
https://crypto.stackexchange.com/questions/6713/low-public-exponent-attack-for-rsa
http://www.loyalty.org/~schoen/rsa/
https://blog.trailofbits.com/2019/07/08/fuck-rsa/

Link to this headingChoosing P and Q

Random Prime Number Generation:

import os, math, random def rabinMiller(possible_prime): exp = possible_prime - 1 t = 0 while exp & 1 == 0: exp = exp//2 t +=1 for k in range(0,128,2): test_number = random.randrange(2, possible_prime-1) #a^s is computationally infeasible. we need a more intelligent approach #v = (a**s)%n #python's core math module can do modular exponentiation mod_prime = pow(test_number, exp, possible_prime) #where values are (num,exp,mod) if mod_prime != 1: i=0 while mod_prime != (possible_prime-1): if i == test_number-1: return False else: i = i+1 mod_prime = pow(mod_prime, 2, possible_prime) return True def is_prime(possible_prime): #lowPrimes is all primes (sans 2, which is covered by the bitwise and operator) #under 1000. taking n modulo each lowPrime allows us to remove a huge chunk #of composite numbers from our potential pool without resorting to Rabin-Miller lowPrimes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 ,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179 ,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269 ,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367 ,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461 ,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571 ,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661 ,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773 ,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883 ,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997] #Check If even if (possible_prime & 1 != 0): #Check primes under 1000 for p in lowPrimes: if (possible_prime % p == 0): return False #Check rabinMiller return rabinMiller(possible_prime) return False def generate_probable_prime(bits=1024): print("Generating a probable prime with {} bits".format(bits)) #Maximum number of attempts to get a prime number max_attempts = int(100 * (math.log(bits, 2) + 1)) for x in range(max_attempts): #Get X bytes of random data #And Convert into an integer random_int = int.from_bytes(os.urandom(bits // 8), "big") #Set the Highest bit of the random int random_int |= (1 << bits) print("-", end="", flush=True) #Check if is prime if is_prime(random_int): return random_int raise Exception("Could not generate Prime") if __name__ == '__main__': p = generate_probable_prime() q = generate_probable_prime() print(p) print(q)

Link to this headingKey Generation

Pick Two Primes:

Random Prime Number P = 61 \\ Random Prime Number Q = 53

Compute Public Key N:

Public Key N = P*Q = 3233

Compute Phi/Order:

Phi(N) = Phi(3233) = (P-1)*(Q-1) = (61-1)*(53-1) = 60*52 = 3120

Choose Exponent greater than 1 and less than Phi:


Encryption Exponent e = 17 //Needs to be less than Phi

Common exponents:


    

  • 3
    • 

  • 5
    • 

  • 17
    • 

  • 257
    • 

  • 65537
    • 



Compute Decryption Exponent:


Get modinv(E, Phi(n)) = modinv(17, 3120)
Find d where (d * 17) % 3120 == 1

GCD(17, 3120) = 1 // Make sure that this is true

To Find d 
(d * 17) % 3120 == 1 -> 17*x + 3120*y == 1
Find an x and y that makes the it true
17*x + 3120*y == 1 -> 17*x -1 = -3120y -> (1/3120) - (17/3120)*x = y
Find an x and y where they are integers of the line (1/3120) - (17/3120)*x = y

Test y from 1 to 100 and see which are integers

Public Key:


(N=3233, e=17)

Private Key:


(N=3233, d=2753)

Link to this headingAttacks


P and Q Attacks:


    

  • If Alice reuses any known prime then you can factor with GCD Test Certificates for Widely Used RSA Moduli attack
    • 

  • If p and q share half of the upper bits with each other can factor with Fermat’s method.

      

    • They are close together to the square route and can be calculated that way.
      • 

    

    • 

  • If p or q have too many zero bits they can be factored with Coppersmith’s method.
    • 

  • If p-1 or q-1 has small prime factors then can use Pollard p-1 to factor.
    • 



Exponents Attacks:


    

  • If d < sqrt(sqrt(N)) can be recovered using continued fractions
    • 

  • Chinese Remainder therm is subject to fault attacks
    • 

  • If e is small like 3 related messages can be decrypted or forge signatures

      

    • A small e makes it possible that the message taken to the 3rd power is not greater than N. This makes it possible to figure out the message by
      • 

    

    • 



Link to this headingFermat’s Theorem Example


Since N = p \* q there exist either p or q is less than the sqrt of N.


N = a^2 - b^2 = (\dfrac{p+q}{2})^2 - (\dfrac{p-q}{2})^2

Try to factor N = 5959


First round:


a = ceiling(sqrt(5959)) = 78
b^2 = a^2 - N = 6084 - 5959 = 125
b = 11.18

Round 2 since not b is not a integer


a = 79
b^2 = a^2 - N = 6241 - 5959 = 282
b = 16.79

Round 3 since not b is not a integer


a = 80
b^2 = a^2 - N = 6400 - 5959 = 441
b = 21

Code


from decimal import *
getcontext().prec = 20

def is_int(a):
	return a == a.to_integral_exact()

N = Decimal(2391788449 * 3264702239)

# Find Ceiling of p or q
max_prime = N.sqrt().to_integral_exact(rounding=ROUND_CEILING)
print(f"{max_prime=}")
#max_prime=Decimal('2794365242')

test = (max_prime ** 2) - N
while not is_int(test.sqrt()):
	max_prime += 1
	test = max_prime**2 - N

p = max_prime - test.sqrt()
q = max_prime + test.sqrt()

print(f"N factors: {p=}, {q=}")
#N factors: p=Decimal('2391788449'), q=Decimal('3264702239')

Link to this headingWiener Attack


The decryption exponent d < N^(1/4) if d is a small number than it is possible to retrieve the decryption exponent.


from decimal import Decimal, getcontext
from Crypto.PublicKey.RSA import  construct

#Continued Fractions
def cf(n, d):
    res = []
    q, r = divmod(n, d)
    while r != 0:
        res = res + [q]
        prev_r = r
        q, r = divmod(d, r)
        d = prev_r
    return res + [q]

getcontext().prec = 50


N = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
enc_exp = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
cipher_text = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
q0 = 1

list1 = cf(enc_exp,N)
#print(list1)
for i in list1:
	q1 = i

	for r in range(30):
		for s in range(30):
			#Check Possible decryption exponent
			d = r*q1 + s*q0

			#Check if P and Q are valid
			try:
				rsa_key = construct((N, enc_exp, d))
				if rsa_key.p * rsa_key.q == N:
					print(f"{rsa_key.p=}, {rsa_key.q=}")
					exit()

			except ValueError:
				pass
	q0 = q1


Link to this headingLLL Attack


Link to this headingCoppersmith Attack


Assume that you know a partial part of the message. This can be represented as such.


c = (m)^e \pmod{N}
c = (m_0 + x_0)^e \pmod{N}

Example:


Creating Primes:


#This is for setting the top 1024-500 bits of the 
tmp = randint(2**1023, 2**1024)
e = 65537

#print(math.log2(str(tmp*0xDEAD)))
#p and q are about 1039 bits long each
#the randint(2, 2**500) fills the bottom with the bottom 500 bits of the prime
# Then lets actually pick a prime number for RSA to function correctly
p = next_prime(0xDEAD*tmp+randint(2, 2**500))
q = next_prime(0xBEEF*tmp+randint(2, 2**500))
N =  p*q

Coppersmith Attack:


#Number of hidden bits
hidden = 500
#Since the 0xDEAD and 0xBEEF are known values for the prime generation they can be factored out. 
# Then the square route is in range of the original tmp value that was used to generate the top half of the primes
tmp = isqrt((N)/(0xdead * 0xbeef))
print "tmp: ", tmp

#q_approx is the approximate upper bound for the max either p or q can be.
q_approx = 0xbeef*tmp - 2**500
q2_approx = 0xdead*tmp - 2**500

#Lets take the minimum because we only need to find the lowest factor then use gcd to find the bigger factor
q_approx = min(q_approx, q2_approx)
print q_approx
 
# Lets create the Output range of RSA function. This is mod N so only numbers from 0-N excluding the p and q
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')

#Lets start the first test at the lowest possible number to test
f = x - q_approx

#Set as the number of unknown digits 
#This is Coppersmith algorithm for finding small roots using the LLL algorithm
roots = f.small_roots(X=2**hidden, beta=0.1)

for delta in roots:
	# For every root lets check the test value of q
	print('delta', delta)
	print('q_approx - delta', q_approx-delta)
	# Lets subtract the change from the max value that q can be to find the test q
	q = q_approx-delta
	# Find other prime through GCD
	p = int(N)/int(q)
	# Find private exponent through Chinese remainder function
	d = inverse_mod(65537, (p-1)*(q-1))
	print("d", d)
	#Decrypt the cipher text
	decrypted = hex(int(pow(c,d,N)))
	print('flag =', decrypted[2:-1].decode("hex"))

Link to this headingFranklin-Reiter attack


This attack works when the Public Exponent is a low number.


https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-Franklin-Reiter


Link to this headingTwin Primes attack


Example Vulnerable Program:



def getTwinPrime(N):
    while True:
        p = getPrime(N)
        if isPrime(p+2):
            return p

def genkey(N = 1024):
    p = getTwinPrime(N)
    q = getTwinPrime(N)
    n1 = p*q
    n2 = (p+2)*(q+2)
    e = long(65537)
    d1 = inverse(e, (p-1)*(q-1))
    d2 = inverse(e, (p+1)*(q+1))
    key1 = RSA.construct((n1, e, d1))
    key2 = RSA.construct((n2, e, d2))
    if n1 < n2:
        return (key1, key2)
    else:
        return (key2, key1)

Given Equations:


N_1 = p * q
N_2 = p+2 * q+2

Derived Equation 1:


\begin{aligned}
N_2 - N_1 &= (p+2 * q+2) - (p * q) \\
   &= ((p+2 * q) + 2(p+2) ) - (p * q) \\
   &= ((p+2 * q)) - (p * q) + 2(p+2) \\
   &= ((p * q) + q + q ) - (p * q) + 2(p+2) \\
   &= ((p * q)) - (p * q) + 2(p+2) + 2q \\
   &= 2(p+2) + 2q \\
\end{aligned}

\\~\\

\dfrac{N_2 - N_1}{2} = p+2 + q

\\~\\

\dfrac{N_2 - N_1}{2} -2 = p + q

Derived Equations:


(p-1)*(q-1) = pq - p - q + 1 \\
(p-1)*(q-1) = N_1 - (\dfrac{N_2 - N_1}{2} -2) + 1 \\
d1 = N_1 - \dfrac{N_2 - N_1}{2} -1 \\
2*d1 = 2*N_1 - (N_2 - N_1) -2 \\
2*d1 = 3*N_1 - N_2 -2 \\
d1 = \dfrac{3*N_1 - N_2 -2}{2} \\

\\~\\

(p+1)*(q+1) = pq + p + q + 1 \\
(p+1)*(q+1) = N_1 + (\dfrac{N_2 - N_1}{2} -2) + 1 \\
d2 = N_1 + \dfrac{N_2 - N_1}{2} -1 \\
2*d2 = 2*N_1 + (N_2 - N_1) - 2 \\
2*d2 = N_1 + N_2 - 2 \\
d2 = \dfrac{N_2 + N_1 - 2}{2} \\

Link to this headingCommon Mod Attack


If the message is encrypted with the same n and different exponents it is possible to recover the unencrypted message.


This only works if message ^ gcd(e1, e2) < n.


Example:


#InCTF 2017

import decimal 
from Crypto.Util.number import *
from cryptopals_lib import bytes_to_int, int_to_bytes


e1 = 9
e2 = 123

def egcd(a, b):
	if (a == 0):
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def neg_pow(a, b, n):
	assert b < 0
	assert GCD(a, n) == 1
	res = pow(a, -1, n)
	res = pow(res, b*(-1), n)
	return res

def nth_root(num_decimal, n_integer):
	context = decimal.getcontext()
	context.prec = 4096	

	exponent = decimal.Decimal("1.0") / decimal.Decimal(n_integer)
	test = context.power(num_decimal, exponent)
	#print(test.to_integral_value())
	return int(test.to_integral_value())


def common_modulus(exp_1, exp_2, n, cipher1, cipher2):
	g, a, b = egcd(exp_1, exp_2)
	if a < 0:
		cipher1 = neg_pow(cipher1, a, n)
	else:
		cipher1 = pow(cipher1, a, n)
	if b < 0:
		cipher2 = neg_pow(cipher2, b, n)
	else:
		cipher2 = pow(cipher2, b, n)
	ct = cipher1*cipher2 % n
	m = nth_root(ct, g)
	return m

def prime_gen():
	while True:
		p = getPrime(1024)
		q = getPrime(1024)
		n = p*q
		phin = (p-1)*(q-1)
		if GCD(e1, phin) == 1 and GCD(e2, phin) == 1:
			return (p, q, n)

if __name__ == '__main__':
	p, q, n = prime_gen()

	#print("p:{}\nq:{}\nn:{}".format(p, q, n))

	flag = bytes_to_int(b"CTF{THIS IS A FLAG WITH TEXT DATA}")

	assert flag < n
	assert flag**e1 > n

	#Check Wrap A Round
	e_gcd = egcd(e1, e2)[0]
	assert pow(flag, e_gcd) < n

	#Generate ciphertexts
	ciphertext1 = pow(flag, e1, n)
	ciphertext2 = pow(flag, e2, n)

	print("C1: {}".format(ciphertext1))
	print("C2: {}".format(ciphertext2))


	message = common_modulus(e1, e2, n, ciphertext1, ciphertext2)
	print("Message: {}".format(int_to_bytes(message)))

Link to this headingCommon Small Exponent Attack


    

  • Also known as Hastad’s Broadcast Attack
    • 

  • If the same message is encrypted many times by the different keys and uses a small exponent
    • 



from Crypto.PublicKey import RSA
from Crypto.Util.number import GCD, bytes_to_long, long_to_bytes
import gmpy2

def crt(list_a, list_m):
	"""
	Reference: https://crypto.stanford.edu/pbc/notes/numbertheory/crt.html
	Returns the output after computing Chinese Remainder Theorem on
	x = a_1 mod m_1
	x = a_2 mod m_2
	...
	x = a_n mod m_n
	input parameter list_a = [a_1, a_2, ..., a_n]
	input parameter list_m = [m_1, m_2, ..., m_n]
	Returns -1 if the operation is unsuccessful due to some exceptions
	"""
	try:
		assert len(list_a) == len(list_m)
	except:
		print("[+] Length of list_a should be equal to length of list_m")
		return -1
	for i in range(len(list_m)):
		for j in range(len(list_m)):
			if GCD(list_m[i], list_m[j])!= 1 and i!=j:
				print("[+] Moduli should be pairwise co-prime")
				return -1
	M = 1
	for i in list_m:
		M *= i
	list_b = [M//i for i in list_m]
	assert len(list_b) == len(list_m)
	try:
		list_b_inv = [int(gmpy2.invert(list_b[i], list_m[i])) for i in range(len(list_m))]
	except:
		print("[+] Encountered an unusual error while calculating inverse using gmpy2.invert()")
		return -1
	x = 0
	for i in range(len(list_m)):
		x += list_a[i]*list_b[i]*list_b_inv[i]
	return x % M



def hastad_unpadded(ct_list, mod_list, e):
	"""
	Implementing Hastad's Broadcast Attack
	"""
	m_expo = crt(ct_list, mod_list)
	if m_expo != -1:
		eth_root = gmpy2.iroot(m_expo, e)
		if eth_root[1] == False:
			print("[+] Cannot calculate e'th root!")
			return -1
		elif eth_root[1] == True:
			return long_to_bytes(int(eth_root[0]))
	else:
		print("[+] Cannot calculate CRT")
		return -1

if __name__ == '__main__':
	message = bytes_to_long(b"Test Message")

	key1 = RSA.generate(2048)
	key2 = RSA.generate(2048)
	key3 = RSA.generate(2048)

	ct1 = pow(message, 3, key1.n)
	ct2 = pow(message, 3, key2.n)
	ct3 = pow(message, 3, key3.n)

	print(hastad_unpadded([ct1, ct2, ct3], [key1.n, key2.n, key3.n], 3))

Link to this headingBrute force


Factor Numbers


Link to this headingOracle Attack


https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-LSBit-Oracle

https://github.com/ashutosh1206/Crypton/tree/master/RSA-encryption/Attack-LSBit-Oracle-variant


Link to this headingEncryption and Decryption


Encrypting a Message:


cipher_text = message ^ e \pmod{N}

Decrypting a Message:


message = cipher_text ^ d \pmod{N}

This works because e and d are modular inverses of each other. They reverse the operation done by the other one.


Link to this headingPadding


If no padding is used then the same input message will always have the same output message.


There are mutable valid paddings. This makes it so that their is mutable valid Signatures for the same message.


Link to this headingFiguring out Public key from Cypher Text


If you know the original message and the Cipher text for two separate messages then it is possible to recover the plain-text.


P_1 ^ e = C_1 \pmod{N} \\
P_2 ^ e = C_2 \pmod{N} 

\\~\\

P_1 ^ e - C_1 = k_2N \\
P_2 ^ e - C_2 = k_2N \\

\\~\\

gcd( P_1^e - C_1, P_2^e - C_2 ) = N


Link to this headingShor’s Algorithm


Source


Work on Quantum Superposition and Quantum Interference


Link to this headingIntroductory Theory


If GCD(A,B) = 1 then A^p = m*B + 1


Example 1:


A = 7
B = 15

7^2 =   3*15+4
7^3 =  22*15+13
7^4 = 160*15+1

Example 2:


A = 42
B = 13

42^2 =   135*13+9
42^3 =  5699*13+1

Link to this headingWhy it works


Using the Introductory theory from above we get the final form of the equation


A^p = m*B + 1
A^p -1 = m*B
A^{p/2} + p/2) -1 = m*B
A^{p/2} * A^{p/2} -1 = m*B
A^{p/2} * A^{p/2} - A^{p/2} + A^{p/2} -1 = m*B
A^{p/2} * (A^{p/2} - 1)  + 1(A^{p/2} -1) = m*B
(A^{p/2} + 1) + (A^{p/2} - 1) = m*B

This means that the two numbers are factors of B. Lets look at the example below


Example (7,15):


7^{4/2} +1 = 50
7^{4/2} -1 = 48

GCD(50, 15) = 5
GCD(48, 15) = 3

Link to this headingWhy doesn’t it work without Quantum Computers?


First Problem:


The first factor below might be a mutable of N and the second is a factor of m. Which is not really helpful.


(G^{p/2} + 1) + (G^{p/2} - 1) = m*N

Second Problem:

Another Reason this might not work is if p is a odd number.

This makes the factors fractions and not whole numbers. Also not really helpful.


But about 37% of the time when a random G is chosen and p is not odd this will break RSA. This means if you can get 10 unique G this goes to 99% chance of breaking N.


Third Problem:

This is the biggest problem. For big numbers it takes a while to find p. Its actually so time intensive that it takes longer to find this p then it does to factor the number.


Link to this headingHow Quantum computers work


A Quantum computer can take many inputs operate a function on them and then get the outputs. You only get one of the outputs randomly biased on weights.


Making Quantum computers work more reliably is up to the algorithm. The algorithm should get the correct answer but all of the wrong answers should destructively interfere with each other.


Example:

So Now we want to test all possible values of p and get the remainder of how much it is over the mutable of N.


Using the Quantum Computer we are able to test all values of p


| 1 -> + |2 -> + |3 -> .... -> | f(G^p) -> |1, G^1 -> + |2, G^2 -> |3, G^3 ... -> | g(> m*N) -> |1, +17 -> + |2,+5 -> + |3,+92 ...


Link to this headingIntroductory Theory Part 2


Lets take a random p value that does not get a remainder of 1. In this case lets choose 42. There is a property for a mutable of p more than a the original guess.


G^p = m*N + 1

G^{42}    = m*N + 3
G^{42+p}  = m*N + 3
G^{42+2p} = m*N + 3

This works by the math below where o is just a new mutable of N.


\begin{aligned}
G^{p+42} &= G^p * G^{42} = (m*N + 1)(m_1*N + 3)  \\
		 &= m * m_1 * N^2 + 3 * m * N + m_1 * N + 3  \\
		 &= (m * m_1 * N + 3 * m + m_1)N + 3  \\
		 &= oN + 3 \\
\end{aligned}

Link to this headingQuantum Fourier Transform


If you put in a single number then the output is a quantum sin wave where the input is the frequency.


If you put in more than one number then the output is the combination of the sign waves of those frequencies.


If you put in more than one number where each are separated by a constant number then they cause destructive interference and are left with the single frequency.


Link to this headingPutting it all together


Using a Quantum computer with the algorithm of testing all values of p. If we just measure the amount that it is bigger than a mutable of N. Then we will get a random remainder number and all of its powers that could result in that remainder.


This means that we get all of the inputs that are of this formula x + i * p. Using a Fourier Transform we can get the period p.


Quantum Fourier Transform:


| 2 -> + |12 -> + |22 -> .... -> | QFT(x) -> |1/p

1/p -> 1/(1/p) -> p

Now lets check the problems from before.


p must be even.

g^(p/2) +- 1 Check if they are a mutable of N


Link to this headingExample Bad


Lets choose a random g smaller than N


Setup:


g = 101
N = 314191

GCD(g,N) = 1

Find p:


g^p = mN +1
101^p = m*314191+1

Use Quantum Computer:


|1 -> + |2 -> + |3 -> .... | 314191 -> | f(G^p) -> |1, G^1 -> + |2, G^2 -> |3, G^3 ... |314191, G^314191 -> | g(> m*N) -> |1, +101 -> + |2, +10201 -> + |3, +87728 ... |314191 ,+153423

Lets assume that we get 307027 when we take a random answer from this.


101^3000 = (2.93040473507818169406e6007)  * 314191 + 307027
101^7347 = (1.78623847854791762404e14720) * 314191 + 307027
101^11694 = (1.0888079261037826305e23433) * 314191 + 307027

Use Quantum Computer:


|3000 -> + |7347 -> + |11694 -> ... | f(QFT) -> |1/4347 -> |2/4347 -> |3/4347 -> ...

Choose a random number from this mutable times and you can get p. But this is ODD and there for we have to choose a new number.


Link to this headingExample Good


Alright lets go a little faster this time. Lets choose a random g smaller than N


Setup:


g = 127
N = 314191

GCD(g,N) = 1

Find p:


g^p = mN +1
127^p = m*314191+1

Use Quantum Computer:


|1 -> + |2 -> + |3 -> .... | 314191 -> | f(g^p) -> |1, g^1 -> + |2, g^2 -> |3, g^3 ... |314191, g^314191 -> | g(> m*N) -> |1, +127 -> + |2, +16129 -> + |3, +163237 ... |314191 ,+295385

{15: 257129, 17403: 257129}


Lets assume that we get 257129 when we take a random answer from this.


127^{15} = (114778904100005530972255754)  * 314191 + 257129
127^{17403} = (9.97612899282997033276e36606) * 314191 + 257129

Use Quantum Computer:


|15 -> + |17403 -> + ... | f(QFT) -> |1/17388 -> |2/17388 -> ...

Final:


127^(17388/2) + 1 = 127^{8694} + 1  \\
127^(17388/2) - 1 = 127^{8694} - 1  \\

\\~\\

GCD(127^(8694) - 1, 314191) = 379 \\
GCD(127^(8694) + 1, 314191) = 829 \\

\\~\\

379*829 = 314191