RSA

The most common Public-Key/Asymmetric-Key algorithm.

In RSA, modular exponentiation, together with the problem of prime factorisation, helps us to build a trapdoor function.

The private key is the secret piece of information or "trapdoor" which allows us to quickly invert the encryption function

In RSA the private key is the modular multiplicative inverse of the exponent e modulo the totient of N

RSA Key Generation, Encryption, and Decryption

Key Generation

\(\text{Select two large primes} \ p \ \text{and} \ q \ \text{such that} \ p \ \neq \ q\)

\(n \gets p \times q\)

\(\varphi(n) \gets (p-1) \times (q-1)\)

\(\text{Select} \ e \ \text{such that} \ 1 < e < \varphi(n) \ \text{and} \ e \ \text{is coprime to} \ \varphi(n) \text{ so that there is a modular inverse }\)

The most common value for e is 0x10001 or 65537

\(d \gets e^{-1} \mod \varphi(n) \ \ \ \ \ \ \ \ \text{ or by solving } \ \ \ \ \ \ d \times e \equiv 1 \mod \varphi(n)\)

\(PublicKey \gets (e, \ n)\)

\(PrivateKey \gets d\)

Tip

The Keys sizes could be different {512, 1024, 2048, 4096} – the bigger the harder to crack –

Public/Private Key Example

Note

it’s recommended using primes that are at least 1024 bits long, multiplying two such 1024 primes gives you a modulus that is 2048 bits large. RSA with a 2048-bit modulus is called RSA-2048.

\(P \gets PlainText\)

\(C \gets CipherText\)

Enccryption

\(C = P^e \mod n\)

Exponential Complexity

\(\text{without having} \ d \ \text{it's hard to find} \ P\)

\(P = \sqrt[e]{C} \mod n\)

Decryption

\(P = C^d \mod n\)

How ??

\(C^d \equiv (P^{e})^{d} \equiv P^{ed} \equiv P \mod n\)

RSA Digital Signature

Signing

\(\text{Encrypt the Messsage } (M) \text{ with the reciver Public Key } (e_{0}, N_{0})\)

\(C = M^{e_{0}} \mod N_{0}\)

\(\text{Calculate the hash/digest of the message: } H(M) \text{ and encrypt it with my Private Key (sender)}\)

\(S = H(M)^{d_{1}} \mod N_{1}\)

Verifying

\(\text{The receiver can decrypt the message using their Private Key}\)

\(m = C^{d_{0}} \mod N_{0}\)

\(\text{calculate the hash/digest of the received message: } H(M) \text{ and compare it to } s \text{ which calculated using the sender Public Key}\)

\(s = S^{e_{1}} \mod N_{1}\)

\(\text{assert } H(m) == s\)

Security of RSA

1. Factorizable modulus (n)

Note

RSA relies on the difficulty of the factorisation of the modulus N

Example

n = 3035587984187658979049949373626692753001568649909
e = 65537
c = 2325265045258945866725599932004757358522079216082
  

\(Factors(n) = 101^5 \times 523^2 \times 58749233^2 \times 553113283^2\)

\(\varphi(n) = \varphi(101^5) \times \varphi(523^2) \times \varphi(58749233^2) \times \varphi(553113283^2)\)

\(\varphi(n) = (101^5 - 101^{5-1}) \times (523^2 - 523^{2-1}) \times (58749233^2 - 58749233^{2-1}) \times (553113283^2 - 553113283^{2-1})\)

\(\varphi(n) = 2999785884764688112542820667580382134861795321600\)

\(d = e^{-1} \mod \varphi(n)\)

\(m = c^{d} \mod n\)

Using sagemath

sage: factor(n)
# 101^5 * 523^2 * 58749233^2 * 553113283^2

sage: euler_phi(n)
# 2999785884764688112542820667580382134861795321600

sage: d = pow(e, -1, euler_phi(n))
# OR
sage: d = inverse_mod(e, phi)
# 1806545147014552244164976213559707067743798735873

sage: m = pow(c, d, n)
# 3545233643812369207

sage: bytes.fromhex(hex(m)[2:])
# b'13371337'
  

2. Small exponent (e)

Example

n = 882564595536224140639625987659416029426239230804614613279163
e = 3
c = 44558912828464771189852064661426808927281111089587712743 
  

\(\text{Since } \ c = p^{e} \mod n\)

\(\text{So } \ p = \sqrt[e]{c} \mod n\)

Using sagemath

sage: c.nth_root(3, True)
# (3545233643812369207, True)       # it has to be True !! 

sage: bytes.fromhex(hex(c.nth_root(3, True)[0])[2:])
# b'13371337'
  

3. Small private key (d)

Wiener's theorem

\(\text{Let } n = pq \text{ with } q < p < 2q. \ \text{ Let } d < \frac{1}{3} n^{\frac{1}{4}}\)

\(\text{Given } n \text{ and } e \text{ with } ed \equiv 1 \ (mod\ \varphi(n)) \text{ , the attacker can efficiently recover d }\)

Example

n = 0x98020da1cd75a815cb2ea78731feddaf930540cd6089807fa2ce5c38450fbcdd7948cc3950fb6cfb7d53360f09693546f574340a6fb229539f62a0d6c93cf7ab26817f01ece66b909b76eba0366877b64be776c850ca11b04dd5f869e59b415ab34c9d4fd00065b38ca3da4043c9b737c17be29e8214d62c6ea27dcfdceeda19be3dceef8b514f429659a4201d5f767235082b416f69101fd0cc7ccb4a8b4304ba8715eb70beba8b99a0a78c75a047345d606a69ba30970ed2fc4a4117c975d2016095efee91d8f29b2a97ad80b48212955049c49cc8bb7d64c1304be6cb710798fa0e9a68006efd3619a5cca4a152f072136040f291dfbb15615be354a2226d
e = 0x834730dff6696bd9560b1c3b590b6f0ce57873e0419f8c39fc57129b8d45795616ab9e19495ba3cf4021e43f7be831d986e5dc374f8310eb98b41da2db62dfa70baf7e6b0b812850f1f0f8a4e943deabd1ce78b36173626576ea740f8216184c0472be520b978081ced49172cd3ce0a6b0c1389bcf8127efd42a20c00ed754da90d4feddbf3923963f289c090eb6e9174377a86b8f02c49e818db55e99f4e92befd28eaef8ec56f4eb7ea688256ed6ae20ac370cbb6890bc6508c14445581802235cae1365a4d348d462d01ab12287caca602580b5bed3aaf29d10c78638c5d838c9111a7f1ff0cd479086b65d97f8f9e30db5e7642b94d32799dddccc067373
c = 0xe21de316dde3f855ee12d699f7c83374ad8b886c1d5563e0ab3ff4fc212101962db8adee80ef2ca146bdcdb181e70fc0b89174d9ce74608a9d64d4e1d422207a89c8951a0dbdc73a76117cbe16a2b08e5c3a1ab0f31d6befa9bf6df6a4aa3354fecb6b751e61394c27e0f7d4f022bd56b0948119084fec178c716293b106ba8bb1bc07a045f4eb3d44bbdf27955f5b4446e04c37e54fa7fda10b6ab6b1a736865fb189985e80736dd507e91b10edcc5d6197b6f1cf37692913b52fb772997d5a417c852a31521fabcdcee209355bc14b9bea49f6dbb50a96bd97803486559d896e2274506d8aaf2ce5159217f302c0a3fa1e86b5409c68b8982627cfa50e572
  

Big Thanks to orisano

from Crypto.Util.number import *
import owiener

d = owiener.attack(e, n)

long_to_bytes(pow(c, d, N))
# b'13371337'
  

Encryption with multiple different exponents

Example

n = 21068309492183809789891952276557604449981629795930147243582403378665878487879254152133466782955676270709173380248244745757959383636842986220258252114469226878147550354975386522434762471514228133076204045847317982761324736433177120622266373049928404638470748357179536706098889074434169289046193593808252250331821544151318049451392028296091565444896477098766588798017317367072459718236488638954923592271664639581309312438878187988755290853044507211345148418959934057551058963743797490797782707797177396538960266033836461616412903292917845823772764906008193494662258552245781674964109957701949719906413325250654484076397

# the receiver private key, where he expect to decrypt the message with
d =  19602718711786995946839670200343769231899229773963234792852400830436058080685737212395967735646600052417778878813150862975553462859261357915969722407740734494647013527407252687261042555930155531970043949336676319526680497706978873938455512089942082457919485074447926961327159588947415580625582388013482547579474088509449256221453170334623047864325209173600307690519092701672368375939732215641929253869633928127857413467181885211793148220486335471982852044132533882366032988688974831546213660980672648176350845470613278989917877353300088081498041957314715085077511568239085729640151310505216113844471467154269887107777
# the receiver public exponent used in generating (d)
e = 0x10001

# but these are the exponents that used for encryption instead !! 
exponents = [110059, 94603, 83243, 71237, 110731]

c5 = 10233787827865692277934634962907296044097817679155019239740226585598320947392719245121573980234599498872785686931195627011035378353300181235509314890665220769412705527800863926831076117303941626475601421989803666372985919958904956893709001136051149258456600903782963070615351639057903447626626643417786754138827115608819080134688350171254157270112771284801449923977489391574731612848906889660334934772180429038668005323892636972282704204235647148555338635816410764913020447266754435149012266377493361008407290358720418021346452628408371946471843322466974149740998323156526380754314565414967513057673996836357836230639
  

\(C_{1} = P^{e_{1}} \mod n \ \ \ \ \ \ \ \ \ C_{2} = C_{1}^{e_{2}} \mod n \ \ \ \ \ \ \ \ \ C_{3} = C_{2}^{e_{3}} \mod n \ \ \ \ \ \ \ \ \ \text{.....}\)

\(\text{So } \ C_{5} = P^{e_{1} \times e_{2} \times e_{3} \times e_{4} \times e_{5}} \mod n\)

\(\text{Assume that } E = e_{1} \times e_{2} \times e_{3} \times e_{4} \times e_{5}\)

\(\text{And we know that } \ e \times d \equiv 1 \ (mod\ \varphi(n)) \ \ \ \text{ So we can find the inverse of the equation } \ C^d \equiv (P^{e})^{d} \equiv P^{ed} \equiv P \mod n\)

\(\text{From that } \ C_{5}^d \equiv (P^{e_{1} \times e_{2} \times e_{3} \times e_{4} \times e_{5}})^{d} \equiv P^{Ed} \equiv P \mod n\)

\(\text{So we need just to find a proper value of } d \text{ that allow as to inverse the equation, and lets call it } D\)

\(D \times E \equiv 1 \ (mod\ \varphi(n)) \ \ \rightarrow \ \ D = E^{-1} \mod \varphi(n)\)

\(P = C_{5}^{D} \mod n\)

\(\text{But how can we find } \varphi(n) \text{ ?? }\)

\(\text{From the relation } \ ed - 1 = k \varphi(n) \ \text{ we can decode the message without computing } \varphi(n) \text{ or factoring } n\)

How ??

Note

Am not a mathematician, so correct me if my derivation were wrong ^^

from Crypto.Util.number import *
from factordb.factordb import FactorDB

exponents = [106979, 108533, 69557, 97117, 103231]

E = 1
for e in exponents:
	E *= e

D = pow(E, -1, e*d-1)

print(long_to_bytes(pow(c5, D, n)))
  

3. p & q are too close primes

\(\text{If } \ p - q < n^{\frac{1}{4}} \ \text{ Fermat's factoring algorithm can factor } n \text{ efficiently }\)

Fermat's factoring algorithm

Fermat's factoring algorithm uses the fact that :

\(n = pq = (\frac{q-p}{2})^2 - (\frac{q + p}{2})^2 = x^2 - y^2\)

where

\(x = \frac{q-p}{2} \ \ \text{ and } \ \ y = \frac{q + p}{2}\)

now n can be factorized as such:

\(n = (x - y) (x + y)\)

Fermat's algorithm to find one of the factors works as follows :

\(\text{Let } a = \sqrt{n}\)

\(\text{Let } b = a \times a - n\)

\(\text{While } b \text{ is not a perfect square }\)

\(a = a + 1\)
\(b = a \times a - n\)

\(\text{Return } \ \ a - \sqrt{b}\)

n = 623638407712431496359236149597697352181528394828691752961343211576226278228768259500340926585888295920588585734080730509025185039264455939509581732375255840540506831547162510684659955362404967112062634388278667879022444787883296787965360666350137688806154494287138338304976195257034444907662265166640381136294834109761167325116771368910919640179742522554966379838034067903637554798031981429314326082786431037551137670273985042819535151519289747741410882268918726725260613682805428551347358259370729791903514182189678652055918069903723053132283638024935014025002942284311594330517961388344726353762685472727270412492175797734245037877148536808214348023869940978760675037161758519037027108067523495893125210748177034197866146841779233191099747563671692050540132779458817241840643958300912998755399515499195773905832851380821134844365591086139050308094135789414910256111130510437280185358948813392431603916154687200272708551052296651216706289100765840295517201212463776401710083522099639871722927152803614558415144219163699564699364647327014627046778228353001519270104956716039902852994946589312707323371045967715329636295087677793288011347583317870650300405089521879832459907782448310572120014094482603215107231129705072164964596879619
e = 65537
c = 507707316956856583769471430485832738953506524948699954656977443679138725045160425449928634990777003401765632882777838612716897801498284998085729528780601485098388219196091867542173113275295699356256460983799067018774862094409818694269923445109604249897742070330007611950169418244958978177432940954418491829660178634810075561734910943919648214360538394874067330159582729093439923258167427091976199693416762759451460031751129054120741167440960105021125604267087370852041782743182257849892284194726541356784362597463098253626139710780339718651813979427622201306856952862198408407590669160847019262944252902549840669472508206077951771141160712471008043503331168204477819239134181226108052686045741807881994843917725180705363584029597947359199958546688436303286984234117384447188868214214601865845978317613495366130649936948913672588046376169896363518778120445689839185305712863895215264121311415693921279258861941241537929263452975823387393144415912771600613896555605762801838669117563378984335967621558215328831214341011037718423134480105947204994888024676555586853981640512087441797040651431882187154569436788971650902408725706765307671082071794709270098347068689884786269119713804261506919244050219108935823476983213524703306611869215
  

from Crypto.Util.number import long_to_bytes,inverse
from sympy.ntheory.primetest import is_square
import sympy

def fermat(n):
	a = int(sympy.sqrt(n))
	b = a * a - n

	while not is_square(b):
		a += 1
		b = a * a - n

	else:

		p = int(a - (sympy.sqrt(b)))
		q = n // p

		if p * q == n:
			return p,q


p,q = fermat(n)
phi = (p-1)*(q-1)
d = inverse(e,phi)

print(long_to_bytes(pow(c,d,n)))
# b'13371337'
  

References

https://mathsci.kaist.ac.kr/cms/wp-content/uploads/2017/11/NumberTheory_Sage.pdf