Implementing RSA in python

Question

i am trying to implement RSA in python(i am new to python) for my course, the problem i have is the code i have written does not work for numbers with more than 4 digits. any idea why this is happening? please advice

p =0
q=0
n=0#modules
phyPQ = 0
e = 0 #public key exponent
d = 0#private key exponent
c = ''
m = ''

def getPrimes():
    global p
    global q
    p = long(raw_input("Enter first prime p :   "))
    q = long(raw_input("Enter second prime q :  "))

def computeModules(prime1,  prime2):
    global n
    n = prime1 * prime2
    print "Modules is = "+ `n`
    return n

def computePhyPQ(prime1,  prime2):
    global phyPQ
    phyPQ = (prime1 -1) * (prime2 -1)
    print "The phyPQ is " + `phyPQ`

def computePublickeyExponent(x):
    pubKeyExponentList= []
    for i in range(1, x):
        if  x % i != 0: 
            pubKeyExponentList.append(i)
    print pubKeyExponentList
    global e
    e =  long(raw_input("Pick a public key exponent from the list above :  "))

def computePrivateKeyExponent(phyQP,  pubKeyExpo):
    flag = 1
    count = 0
    while flag == 1:
        count = count + 1
        if (count * phyQP + 1) % phyQP == 1:
            result = (count * phyQP + 1) / float(pubKeyExpo)
            if result % 1 == 0:
                global d
                d = long(result)
                print 'The private key exponent exponent is:' +  `d`
                flag = 0

def encryptMessage(exponent,  modules):
    #c= m ^e mod n
    global c
    message= long(raw_input("Enter a value to be encrypted:"))

    c = long((message ** exponent) % modules)
    print'The encrypted message is :' + `c`

def decryptMessage(modules,  privateKeyExpo, cryptedMessage):
    #m = c^d % n
    global m
    m = (cryptedMessage ** privateKeyExpo) % modules
    print 'message after decrypting is :' + `m`

def mainMethod():
    getPrimes()
    computeModules(p, q)
    computePhyPQ(p,  q)
    computePublickeyExponent(phyPQ)
    computePrivateKeyExponent(phyPQ, e)
    encryptMessage(e, n)
    decryptMessage(n, d, c)

mainMethod()

Are you saying that you're required to reimplement it?

Ignacio Vazquez-Abrams
– Ignacio Vazquez-Abrams

2010-07-22 19:02:27 +00:00
Commented Jul 22, 2010 at 19:02 — Ignacio Vazquez-Abrams
– Ignacio Vazquez-Abrams, Commented Jul 22, 2010 at 19:02

Greg Hewgill · Accepted Answer · 2010-07-22 20:06:30Z

4

Your problem is most likely in your use of floating point arithmetic:

        result = (count * phyQP + 1) / float(pubKeyExpo)

In this algorithm, it will be important to use arbitrary precision integer arithmetic throughout.

The three-argument version of pow() will be useful in a few places in your implementation. pow(x, y, z) calculates (x ** y) mod z for arbitrary-precision integers.

edited Jul 22, 2010 at 20:06

answered Jul 22, 2010 at 19:05

Greg Hewgill

1.0m192 gold badges1.2k silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Daniel Stutzbach Over a year ago

Minor nitpick: Python's float type is actually C double under the hood (i.e., double precision floating point arithmetic).

Greg Hewgill Over a year ago

@Daniel Stutzbach: Thanks, fixed that.

Perception · Accepted Answer · 2012-05-23 03:45:32Z

3

c = long((message ** exponent) % modules) is not a proper implementation, since it is prohibitively slow.

You could replace it with square-and-multiply exponentiation, sliding-window exponentiation, or Montgomery powering ladder.

A good example can be found here: http://code.activestate.com/recipes/572196-rsa/

edited May 23, 2012 at 3:45

Perception

80.8k19 gold badges190 silver badges197 bronze badges

answered May 22, 2012 at 18:41

Raullen Chai

3152 silver badges2 bronze badges

Comments

Community · Accepted Answer · 2020-06-20 09:12:55Z

0

You cannot use normal numeric calculations for encryption. Numbers typically has an exponent of 1000. Use a python library such as gmpy2 that can handle calculations with huge integers

import gmpy2 Then, for example, change:

result = (count * phyQP + 1) / float(pubKeyExpo)

to:

result = gmpy2.f_divmod(count*phyQP + 1, pubKeyExpo)

if result[0]>0 and result[1]==0:

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jul 28, 2013 at 2:58

Kris van der Merwe

213 bronze badges

Collectives™ on Stack Overflow

Implementing RSA in python

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related