RSA
RSA¶
- 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/
Choosing 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)
Key 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:
Private Key:
Attacks¶
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
Fermat's Theorem Example¶
Since N = p \* q there exist either p or q is less than the sqrt of N.
Try to factor N = 5959
First round:
Round 2 since not b is not a integer
Round 3 since not b is not a integer
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')
Wiener 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
Coppersmith Attack¶
Assume that you know a partial part of the message. This can be represented as such.
Using the Lattice Reduction using LLL
TODO
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"))
Franklin-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
Twin 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:
Derived Equation 1:
Derived Equations:
Common 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)))
Common 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))
Oracle 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
Encryption and Decryption¶
Encrypting a Message:
Decrypting a Message:
This works because e and d are modular inverses of each other. They reverse the operation done by the other one.
Padding¶
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.
Figuring 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.
Shor's Algorithm¶
Work on Quantum Superposition and Quantum Interference
Introductory 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
Why it works¶
Using the Introductory theory from above we get the final form of the equation
This means that the two numbers are factors of B. Lets look at the example below
Example (7,15):
Why 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.
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.
How 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
Introductory 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.
This works by the math below where o is just a new mutable of N.
Quantum 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.
Putting 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:
Now lets check the problems from before.
p must be even.
g^(p/2) +- 1 Check if they are a mutable of N
Example Bad¶
Lets choose a random g smaller than N
Setup:
Find p:
Use Quantum Computer:
Lets assume that we get 307027 when we take a random answer from this.
Use Quantum Computer:
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.
Example Good¶
Alright lets go a little faster this time. Lets choose a random g smaller than N
Setup:
Find p:
Use Quantum Computer:
{15: 257129, 17403: 257129}
Lets assume that we get 257129 when we take a random answer from this.
Use Quantum Computer:
Final: