Cracking RSA Ciphers That Have A Low-exponent
Cracking RSA Ciphers That Have A Low-exponent
In RSA, we have:
The (mod N) part provides a core part of the security of the method. But when happens when M^e is less than N. Well, the cipher is easily cracked.
Normally, in RSA, we select two prime numbers of equal length (p and q), and then multiply these to give a modulus:
We then compute the cipher as:
But, if M^e≤N, then:
The message can be determined from:
For example, if e=3, we take the 3rd root of C. So, if we use a value of M^e that is less than N, and it is easy to recover the message with [here]:
m=libnum.nroot(C,e)
A sample run for a modulus of 128 bits is [here]:
Bob sends Alice a cipher using the RSA method. The cipher is 7446927644895231780144668992 and the public modulus is 114478088404552905363562514346363776111754070678655925650418939227582265249551089334182599044573960040630340706372893593053482627694097935698916862306537210729765728734386595471533687305757272884429400174867808817969676999360799494158594543289037055131414660873402975984872690402174487054555607828223347368227. The value of e is 3 and is a fairly low value. Using this information, can you crack the cipher?
Answer:
For e=3, we take the 3th root to get: 1952805748
Decipher: b'test'
To check, the values used are:
p= 10244484350584956851844144341883232438302678216936882432385982343615525362482979291948437834301744027956476091678423337497588351914806792501874519064043057
q= 11174607182450939302330141097267322131453463774007049882487566249157769228054758728218021547101458590443227509772010588653746282582143032156500321160657811
Conclusions
Luckily, these days, we use a public exponent of 65,537, and which should always be able to produce a large enough value of M^e. Along with this, we can use padding values, in order to make sure M is a large enough integer. So, can you find the Scottish city:
Bob sends Alice a cipher using the RSA method. The cipher is 24670351051808916577942700378012098504302911820711 and the public modulus is 19754557587465768176325771420700157256792036864425666563814631850404204199511307814886533386922719764057485498518156882802150069508316689667719286780611595159038263038616721003998561164791559699358374527176321972149874386061176724753751005592996495146669369368122208191810252255218473660533747728352317864388656523889403718954963859600452126233025654270215121701830147222033406532990083481027414110891241085858076139633794120086619184673797244834174916469166607943783692390454244855737747999412234168510023053880151145985449084039644011388574407041705067957327994682638973550495966338034032171023595517638185657884739. The value of e is 3 and is a fairly low value. Using this information, can you crack the cipher?