Cracking RSA With Only A Few Known Bits

Don’t you just love cracking something that seems almost impossible to crack? Let’s say that you are performing a forensic analysis of a…

Cracking RSA With Only A Few Known Bits

Don’t you just love cracking something that seems almost impossible to crack? Let’s say that you are performing a forensic analysis of a computer, and discover an area of memory that stored the private key of an RSA key, but where most of it has been overwritten. Can you recover the key?

Well, in 2009, Heniger and Shacham showed that it was possible to crack RSA using a few known bits from the private key [1]:

They, then — in 2010 — extended this where all the bits were in error [2]:

With RSA, it is possible to factorize the modulus is a few bits are revealed. Coppersmith outlined that n/4 of the most significant bits or the least significant bits were enough — and where n is the number of bits of one of the factors:

So, here’s a challenge:

Bob sends Alice a message using RSA encryption. The cipher is 75541449316495070242557879696629503743001522537266499560274524496366331774484502324312803536957069347438597116013629371261800557177585772784079745825319 and modulus is 489479825646714735998600461521338887292772090989231227086288896281706475049970972496782887640121878736780890843898491859147122908405228176007386739802903. Eve has discovered something about the bits of one of the factors and has a hint of 319214214539164686171337351819297029614072994981198711208874872392464724386404504627554. Discover the message.

For this, we can generate a challenge, and a solution with the following code using Sage. In the following, we will add noise to one of the factors and reveal it as noise [here]:

import sys
bits=512
str=sys.argv[1]
bits=int(str.split(";")[2])
p,q = random_prime(2**bits//2), random_prime(2**bits//2);
p,q = max(p,q),min(p,q); 
N=p*q; 

ZZn = IntegerModRing(N)
e = Integer(65537)
r = (p-1)*(q-1)
ZZr = IntegerModRing(r)
m = ZZn.random_element()
C=m^e

# Create a hint
k=ZZ.random_element(1,10**10); 
noise=ZZ.random_element(1,2**(50))
hint=k*p+noise; 
print(f"Bob sends Alice a message using RSA encryption. The cipher is {C} and modulus is {N}. Eve has discovered something about the bits in the cipher, and has a hint of {hint}. Discover the message.") 

print("\n\nAnswer:")
x=PolynomialRing(Zmod(N),"x").gen(); 
f=x+hint; 
sr=f.small_roots(beta=0.5)
if sr: 
 kp=hint+sr[0]; 
 p=gcd(N,kp)
 print (f"\nDiscovered p={p}")
 d = ZZr(e)^-1
 m=C^d
 print ("m=",m)
else: 
 print ("\nfail!")
print ("\n\nChecking answer")
print ("p=",p)
print ("q=",q)
print ("m=",m)

A sample run is [here]:

Bob sends Alice a message using RSA encryption. 
The cipher is 23503235633650868879391846652160059045978291684614301685587828912412806648036034816566129699979597164094079413216886439761353683461282738770798754348791 
and modulus is 51241199387405805624636718133492338467678448748492993981087100986117627844604916559156268921810638741003986553568570485296290865475746272625686217377789. 
Eve has discovered something about the bits in the cipher, and has a hint of 233468272075599305685392968157959823314780706916785275009109736904155632848794728751035. Discover the message.

Answer:
Discovered p=52011712826696704689879676704732232175680371508926315686839450681135664987611
m= 19125697439245463985696979663322193447408474147959901243694265358898195562627896425594199558167134136004478674044111366190984507513237642659261274421142

Checking answer
p= 52011712826696704689879676704732232175680371508926315686839450681135664987611
q= 985185770715564514906184421805509973219957182000520903200109401113387611399
m= 19125697439245463985696979663322193447408474147959901243694265358898195562627896425594199558167134136004478674044111366190984507513237642659261274421142

Conclusions

So can you crack:

Bob sends Alice a message using RSA encryption. The cipher is 1504351686363797770622363711079764929669404949100595906289647900595822557041212232183021741650089467730403742444761990545389751311146175578427581066341903094573002590712469062420065553684806091788888488346488965586942241706926411818220350902856338786438253942826909849564881262157856161071585419751621263889 and modulus is 3132739919312893114814391229517879822224932523327286173151995470291649435048596045670402947949936287875887716518831249486446407937095503240622469075197660121127658844459524919789956465405662681712962004966765447931665793715365401722813385355647590613137762693080076236724183777711096257952513081300777221933. Eve has discovered something about the bits of one of the factors and has a hint of 11219140953827883744122876380340816659324486408708977858241219766873274477473739272726156672929357344241351749213746018260405821150619654930547962320712913287031544. Discover the message.

Answer begins with …p= “1813061…” and m = “234669…”

References

[1] Heninger, N., & Shacham, H. (2009). Reconstructing RSA private keys from random key bits. In Advances in Cryptology-CRYPTO 2009: 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings (pp. 1–17). Springer Berlin Heidelberg.

[2] Henecka, W., May, A., & Meurer, A. (2010). Correcting errors in RSA private keys. In Advances in Cryptology–CRYPTO 2010: 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15–19, 2010. Proceedings 30 (pp. 351–369). Springer Berlin Heidelberg.