RSA Implementation Running on Python 3.6

rsa_p36.py

"""
Implementation of RSA cryptography 
using samples of large numbers
"""
import random
import sys
import math

from random import randrange

def rabinMiller(n, k=10):
    if n == 2:
            return True
    if not n & 1:
            return False

    def check(a, s, d, n):
            x = pow(a, d, n)
            if x == 1:
                    return True
            for i in range(1, s - 1):
                    if x == n - 1:
                            return True
                    x = pow(x, 2, n)
            return x == n - 1

    s = 0
    d = n - 1

    while d % 2 == 0:
            d >>= 1
            s += 1

    for i in range(1, k):
            a = randrange(2, n - 1)
            if not check(a, s, d, n):
                    return False
    return True

def isPrime(n):
     #lowPrimes is all primes (sans 2, which is covered by the bitwise and operator)
     #under 1000. taking n modulo each lowPrime allows us to remove a huge chunk
     #of composite numbers from our potential pool without resorting to Rabin-Miller
     lowPrimes =   [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
                   ,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179
                   ,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269
                   ,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367
                   ,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461
                   ,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571
                   ,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661
                   ,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773
                   ,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883
                   ,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]
     if (n >= 3):
         if (n&1 != 0):
             for p in lowPrimes:
                 if (n == p):
                    return True
                 if (n % p == 0):
                     return False
             return rabinMiller(n)
     return False

def generateLargePrime(k):
     #k is the desired bit length
     r = 100*(math.log(k,2)+1) #number of attempts max
     r_ = r
     while r>0:
        #randrange is mersenne twister and is completely deterministic
        #unusable for serious crypto purposes
         n = random.randrange(2**(k-1),2**(k))
         r -= 1
         if isPrime(n) == True:
             return n

     str_failure = "Failure after" + str(r_) + "tries."
     return str_failure


def gcd(a, b):
    '''
    Euclid's algorithm for determining the greatest common divisor
    Use iteration to make it faster for larger integers
    '''
    while b != 0:
        a, b = b, a % b
    return a

def multiplicative_inverse(a, b):
    """Returns a tuple (r, i, j) such that r = gcd(a, b) = ia + jb
    """
    # r = gcd(a,b) i = multiplicitive inverse of a mod b
    #      or      j = multiplicitive inverse of b mod a
    # Neg return values for i or j are made positive mod b or a respectively
    # Iterateive Version is faster and uses much less stack space
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a  # Remember original a/b to remove
    ob = b  # negative values from return results
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lx) = ((lx - (q * x)), x)
        (y, ly) = ((ly - (q * y)), y)
    if lx < 0:
        lx += ob  # If neg wrap modulo orignal b
    if ly < 0:
        ly += oa  # If neg wrap modulo orignal a
    # return a , lx, ly  # Return only positive values
    return lx

def rwh_primes2(n):
    # https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

def multiply(x, y):
    _CUTOFF = 1536
    if x.bit_length() <= _CUTOFF or y.bit_length() <= _CUTOFF:  # Base case
        return x * y
    else:
        n = max(x.bit_length(), y.bit_length())
        half = (n + 32) // 64 * 32
        mask = (1 << half) - 1
        xlow = x & mask
        ylow = y & mask
        xhigh = x >> half
        yhigh = y >> half

        a = multiply(xhigh, yhigh)
        b = multiply(xlow + xhigh, ylow + yhigh)
        c = multiply(xlow, ylow)
        d = b - a - c
        return (((a << half) + d) << half) + c


def generate_keypair(keySize=10):
    p = generateLargePrime(keySize)
    print(p)
    q = generateLargePrime(keySize)
    print(q)

    if p == q:
        raise ValueError('p and q cannot be equal')

    #n = pq
    n = multiply(p, q)

    #Phi is the totient of n
    phi = multiply((p-1),(q-1))

    #Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)

    #Use Euclid's Algorithm to verify that e and phi(n) are comprime
    g = gcd(e, phi)

    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

    #Use Extended Euclid's Algorithm to generate the private key
    d = multiplicative_inverse(e, phi)

    #Return public and private keypair
    #Public key is (e, n) and private key is (d, n)
    return ((e, n), (d, n))

def encrypt(pk, plaintext):
    #Unpack the key into it's components
    key, n = pk
    #Convert each letter in the plaintext to numbers based on the character using a^b mod m
    cipher = [(ord(char) ** key) % n for char in plaintext]
    #Return the array of bytes
    return cipher


def decrypt(pk, ciphertext):
    #Unpack the key into its components
    key, n = pk
    #Generate the plaintext based on the ciphertext and key using a^b mod m
    plain = [chr((char ** key) % n) for char in ciphertext]
    #Return the array of bytes as a string
    return ''.join(plain)

if __name__ == '__main__':
    '''
    Detect if the script is being run directly by the user
    '''
    print("RSA Encrypter/ Decrypter")

    print("Generating your public/private keypairs now . . .")
    public, private = generate_keypair()
    print("Your public key is ", public ," and your private key is ", private)

    message = str(sys.argv[1])

    encrypted_msg = encrypt(private, message)

    print("Your encrypted message is: ")
    print(''.join(map(lambda x: str(x), encrypted_msg)))
    print("Decrypting message with public key ", public ,"...")
    print("Your message is:")
    print(decrypt(public, encrypted_msg))

Give this error

line 214, in
message = str(sys.argv[1])

IndexError: list index out of range

For big numbers waited hours, don't know if it ever would return, replaced plain = [chr((char ** key) % n) for char in ciphertext] with plain = [chr(pow(char, key, n)) for char in ciphertext] returned within milliseconds.

q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
d  = 5910502643142101094010155268323853060995676014483646369518789249525121696368197090523652906132356886194109169434333812851946875508489030509109621090785408764485550222793095970899670772801942244938424168695681373649458693131927836909155655242920064327166085603650717512792289370594893352324251055252461985404095011908795551242997352006435203473432870931894530664909454494842031027849728081156615896441884808673161239734960986808235537343177796872800333685191584724982367870523558343508774072543248141690063061908070632216605268957190235091149665533416149163158866889848771576740235882844710783121360253085219018730173
e = 65537

@balasmeh you need to write your message while executing the program for example

python3 rsa_p36.py "encrypted message here"

This is even weaker than a standard caesar cipher.

Given the public key, I can create the whole substitution table just by encrypting a couple of messages.

@stackola can you propose an attack to the above?

@dendisuhubdy

https://www.0xkasper.com/articles/hacktm-ctf-2020-qualifiers-write-up#rsa-is-easy-1

GOAT

replace lines
184: cipher = [(ord(char) ** key) % n for char in plaintext]
by:
cipher = [pow(ord(char),key,n) for char in plaintext]

193 : plain = [chr((char ** key) % n) for char in ciphertext]
by:
plain = [chr(pow(char, key, n)) for char in ciphertext]

m = input("Enter the text to be encrypted(In English):")
p = 7
q = 23

def gcf(a, b):
while b!=0:
a, b = b, a%b
return a

def encrypt(pk, ptext):
key, n = pk #Unpack the key into it's components

cpr = [(ord(char) ** key) % n for char in ptext] #Convert each letter in the plaintext to numbers based on the character using a^b mod m

return cpr 

def decrypt(pk, cprtext):
key, n = pk #Unpack the key into its components

plain = [chr((char ** key) % n) for char in cprtext] #Generate the plaintext based on the ciphertext and key using a^b mod m

return ''.join(plain) 

def g_puk(tot):
e=2
while e<totient and gcf(e, totient)!=1:
e += 1
return e

def g_prk(e, tot):
k=1
while (e*k)%tot != 1 or k == e:
k+=1
return k

print("Two prime numbers(p and q) are:", str(p), "and", str(q))
n = pq
print("n(pq)=", str(p), "*", str(q), "=", str(n))

totient = (p-1)(q-1)
print("(p-1)(q-1)=", str(totient))

e = g_puk(totient)
print("Public key(n, e):("+str(n)+","+str(e)+")")

d = g_prk(e, totient)
print("Private key(n, d):("+str(n)+","+str(d)+")")

encrypted_msg = encrypt((e,n), m)
print('Encrypted Message:', ''.join(map(lambda x: str(x), encrypted_msg)))
print('Decrypted Message:', decrypt((d,n),encrypted_msg))