| Hosted by CoCalc | Download
# RSA function def rsa(bits): proof = (bits <= 1024) # only prove correctness up to 1024 bits p = next_prime(ZZ.random_element(2**(bits//2 +1)),proof = proof) # choose random prime p q = next_prime(ZZ.random_element(2**(bits//2 +1)),proof = proof) # choose random prime q n = p*q phi_n = (p-1) * (q-1) # Eulers totient function while True: e = ZZ.random_element(1, phi_n) # choose random e between 1 & phi(n) if gcd(e, phi_n) == 1: break # make sure GCD(e, phi(n)) = 1 d = lift(Mod(e, phi_n)^(-1)) # compute integer d return e, d, n # return public keys (e, n) and private key d # Encrypt & Decrypt functions using keys from RSA def encrypt(m,e,n): # encrypt plaintext m with public keys e and n return lift(Mod(m,n)^e) def decrypt(c,d,n): # decrypt ciphertext c with private key d and public key n return lift(Mod(c,n)^d) # Example bit = 1024 # choose number of bits for p & q e,d,n = rsa(bit) # find keys for a 528 bit p & q print "public key e is:", e print print "public key n is:", n print print "private key d is:", d print m = 128 c = encrypt(m, e, n) # encrypt plaintext message m print "our plaintext message is", m print print "our encrypted message is", c print x = decrypt(c, d, n) # decrypt message print "our decrypted message is", x
public key e is: 25154914619692783558068571430639763621001840251801144436870319885362881406933630649562216577079684875519082704044184885952827802241832942154335744241503283365272813358907204172355815938656942415003730001009096157234659693822258517548791362532201358757079804991627449941518154022021881453533276594817542478155 public key n is: 332410743842204136864493223019343512590019575988738053623766811328476430117058755588877037621432752875633770515029051679648805980572858591334806558537508294748269755280003249950618974600305303884096531896396469943658098581804623370534593648623374033955527335181999968807739563768576858599112579339471101502889 private key d is: 280147506585382906913925521124563473509344072292303621876451365566214400196905427859631180171266179218314679253527497642116649532723200722625351768811112906400627536545109737042805631098446853967754970917771736170351839337346086987990738543760220264757067758925728632684237219254058268930457994005146790449507 our plaintext message is 128 our encrypted message is 121927449321839935667706555545723196122424100168032642167896836945546845998467237652079329507671352122458595093868941201324389867325051454302967692528104363543009456730131323800686050353076047486765875817353232426395127104947699010697918312351553034300942783285823385163543822564351552159169115451278946555719 our decrypted message is 128
# Example of attacking RSA when p & q are close def crack_when_pq_close(n): # Input n=pq t = Integer(ceil(sqrt(n))) # t=(p+q)/2, which is close to the square root of n while True: k = t^2 - n # k = difference between t^2 & n (small number) if k > 0: # if t^2 > n s = Integer(int(round(sqrt(t^2 - n)))) # s=(p-q)/2 is a small integer close to sqrt(k) if s^2 + n == t^2: # check for perfect square return t+s, t-s # return p=t+s & q=t-s since N = t^2 - s^2 = (t+s)(t-s) = pq t += 1 # check new t # Test with large n p = next_prime(2^1024) # find p greater than 2^128 q = next_prime(p) # find q = the next closest prime print "(p, q) =",(p,q) print " n = ", p*q # calculate n print print "Our function returns (p, q) =", crack_when_pq_close(p*q)
(p, q) = (179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859, 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224138297) n = 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385831836629839931604913217189678592433570595407204979975197471265575262159281392120754939673496694769217137019932616744005961351912588355903082072668035686677658498973949178916826070183694275197585406793551975206643412017773626759006299241727738775594205159882555660007770314370476543983057729710165883222009486123 Our function returns (p, q) = (179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224138297, 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859)
# Show that phi(n) is hard to find def phi(n): # Euler's totient function count = 0 for k in range(1, n + 1): # check all numbers below n if gcd(n, k) == 1: # check for prime count += 1 # count all cases return count phi(5764937856237580275083579) # try a random large integer