It’s been a long time for both of us since part 3 of this series. So to quietly resume our journey in the beautiful world of mathematics I propose you 4 rather simple topics :
- Multi-prime RSA
- Brute force attack on small secret CRT-Exponents
- Fault attack on signatures
- Twin primes
In part 1 we saw the basics of RSA and how to generate a key pair using 2 prime numbers, but did you know that it’s theoretically possible to use more than 2 primes to generate a key pair ?
By constructing a key using primes, you would have :
For the rest, it’s the same as when using 2 primes.
>>> n = 13*17*89*101 >>> e = 23 >>> phi = 12*16*88*100 >>> d = gmpy2.invert(e,phi) >>> d 587687 >>> m = 31337 >>> c = pow(m,e,n) >>> c 612133 >>> m == pow(c, d, n) True
You might wonder, why would anyone want to do that ? Wouldn’t it make it less secure because the primes would be smaller for the same key size ?
While it’s correct that the factors will be smaller if you use more primes for a given key size, it’s not a major security issue as long as they don’t become too small. If the individual primes can be recovered using known factorization algorithm like ECM, then it’s an obvious bad idea. But otherwise, as long as the total size of the modulus is large enough, factorization is not a threat. The more primes you want to use for your key pair, the larger the modulus should be.
Using more than 2 primes offers performance improvements thanks to the Chinese Remainder Theorem (CRT). The speedup is about with the number of factors used.
Brute force attack on small secret CRT-Exponents
We’ve seen that the CRT can be used to speedup RSA encryption and decryption. In this case we are interested in the decryption process.
In order to decrypt RSA using the CRT, you have to compute :
If the value of is poorly chosen it’s possible that or is so small that you can find it with pure brute force.
How do we know if we have found the correct value for or though ? And what will we use it for ?
From the definition of :
Given any number with :
From Fermat’s little theorem :
So we have :
Or rewritten without the modulo :
As an attacker, you know and and you guess . To verify your guess, you can choose any number and compute :
For a correct value of , this is the same as :
If your guess is incorrect you should get 1 or .
As you can see, correctly guessing leaks a factor of .
This is the same for .
>>> n=95580702933509662811256129990158655210667121276245053843875590334281563078868202152845967187641817281520364662600110239110410372520340630639373679599982371620736610194814723749147422221945978800055101110346161945811520158431287139909125886966214800526831490560384144156085296004816333892025839072729987354233 >>> e=1817084480271067137841898198122075168542117135135738925285694555698012943264936112861815937200507849960517390660821911331068907250788900674614345400567411 >>> m = 7516789928765 # random number >>> for dp in range(1000000): ... f = gmpy2.gcd(m-pow(m, e*dp, n), n) ... if f > 1: ... print(dp, f) ... break ... 187261 8275629468590614667884614599278593237258686111405345888268221129814081809682982742676180514534238891248302334619164139839173447495925780801832743975865311 >>> p = 8275629468590614667884614599278593237258686111405345888268221129814081809682982742676180514534238891248302334619164139839173447495925780801832743975865311 >>> q = n // p >>> p*q == n True
Fault attack on signatures
While we are talking about attacks on RSA CRT, let’s focus on the signing process. This process is identical to decryption but instead of applying it on a cipher text, you apply it on the plain text :
Partial signatures and are calculated modulo and respectively, then the CRT is used to combine both and get the final signature modulo .
In the beautiful world of mathematics everything goes well every time but that’s sadly not the case in the physical world in which our computers do the maths. Faults can occur during operations.
Without faults during the calculation of the partial signatures and , we can do the following observations when verifying the final signature :
The verified signature is congruent with modulo or . This means that is a multiple of and also a multiple of . Which makes it a multiple of and thus,
Now imagine an error occurred on one or more bits during the calculation of . We can observe something interesting :
The verified signature is congruent with modulo but not . This means that is a multiple of but not a multiple of . Thus,
This still holds if the fault occurred during the calculation of
This attack can only work if the attacker knows the plain text . This also means that no random padding is applied to the message before signing.
To counter this, the oracle providing the signatures should verify that they are correct before returning them to the client.
Public key :
n = 95580702933509662811256129990158655210667121276245053843875590334281563078868202152845967187641817281520364662600110239110410372520340630639373679599982371620736610194814723749147422221945978800055101110346161945811520158431287139909125886966214800526831490560384144156085296004816333892025839072729987354233 e = 65537
The faulty signing oracle :
def sign(m, fault=False): # calculates the chinese remainder theorem def chinese_remainder(rests, modulus): from functools import reduce import gmpy2 somme = 0 prod = reduce(lambda a, b: a * b, modulus) for n_i, a_i in zip(modulus, rests): p = prod // n_i somme += a_i * gmpy2.invert(p, n_i) * p return int(somme % prod) p = 8275629468590614667884614599278593237258686111405345888268221129814081809682982742676180514534238891248302334619164139839173447495925780801832743975865311 q = 11549659551128693002436136866773711894878948768217375488402486000729420418015407109031312764052545848546107463625253637067023356033871483957407205015515303 d = 57028735322169588856806818301191294912838800116956991324855687761743930315287292808379020323456337353850356583329296590932364569581501742220294322190489492992620765832487790259098937609311778492158901396624684965933853351733692591081803839662026408989685392901358933693441460040324163121861582078844550186253 dp = d%(p-1) dq = d%(q-1) sp = pow(m, dp, p) sq = pow(m, dq, q) if fault: sq += 1 s = chinese_remainder([sp, sq], [p, q]) return s
>>> # choose a random plain text m >>> m = 1144062044873283369712584268016323072193574476507782486309670943958849941854399472458994589746495512277165641747356772963562804680891066322320937664179951311479733128512661066412624186426754952033049367311462347474835736278522943337011258766432477000856451551683475740137481467325450641265196463953873078111 >>> sign(m) # normal signature without faults 48826985473506942429348825619193527048629734669181322592483292523132023904581030994948425823318125226258131999442356309995646838788180009251813528869344879150322977876831414188780557106363189817128883449429033827496020109623428084253152324191039943271424694994370469425175289337590930279996852887250146794419 >>> sign(m, True) # faulty signature 81223362319896371239841653902911360675773590325559890740901029276412364400437137170775545707395510981182542610557390791827061449907959170362042190965970358905594174189820676645727085090713100254192329083437540099792321809556592051052868235975634208506437252243437261546756934453212754787883663263102660104405 >>> pow(sign(m), e, n) == m # Good signature should return m when verified True >>> pow(sign(m, True), e, n) == m False >>> gmpy2.gcd(pow(sign(m), e, n)-m, n) == n # Good signature doesn't leak a factor True >>> gmpy2.gcd(pow(sign(m, True), e, n)-m, n) == n False >>> gmpy2.gcd(pow(sign(m, True), e, n)-m, n) == p # Because sq is faulty, p is leaked True
You already know that choosing primes that are too close to each other is bad because we can efficiently factor using Fermat’s factorization algorithm. But what if we choose them even closer ?
Twin primes are primes bigger then 2 that are the closest to each other :
The minimum distance between two primes is 2, because primes bigger than 2 must be odd. The only real consecutive primes are 2 and 3.
11 and 13 are twin primes for instance.
The original Fermat’s factorization algorithm becomes unusable in the case of RSA using large twin primes.
In the case of RSA, we’ll have :
This is a simple quadratic equation.
Let’s first calculate the discriminant :
, so , there are always 2 solutions to this equation :
If we take the absolute value of both solutions we obtain the two prime factors of .
>>> n = 11*13 >>> gmpy2.sqrt(n+1) - 1 mpfr('11.0') >>> -gmpy2.sqrt(n+1) - 1 mpfr('-13.0')
>>> n = 881*883 >>> abs(gmpy2.sqrt(n+1)-1) mpfr('881.0') >>> abs(-gmpy2.sqrt(n+1)-1) mpfr('883.0')
I hope this was an easy coming back to the topic. It’s much simpler math than in the previous parts but after such a long break it’s good to get back to basics first 🙂
In the next part we’ll try to move on to more complex attacks.