SharedCaitlin / RSAattacks.sagewsOpen in CoCalc
# 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