RSA encryption python not working with small primes
<p>I have implemented RSA encryption and decryption code which is working for values <code>p,q,d = 61,53,17</code>. I took these values as they are mentioned in wikipedia. I beleive that p and q should be prime and d is chosen such that d and phi(n) are relatively prime.</p>

<p>If I change the values to <code>p,q,d = 3,17,19</code>, my decryption is not working. Can you please help me with this? Here is my code:</p>

<pre><code>#!/usr/bin/python3
# -*- coding: utf-8 -*-

def main():
    str = 'computer'
    p,q,d = 61,53,17
    #p,q,d = 3,17,19
    cipher_text = list()
    plain_text = list()

    for c in str:
        cipher_char = EncryptCharRSA(c, p, q ,d)
        cipher_text.append(cipher_char)


    for x in cipher_text:
        plain_char = DecryptCharRSA(x, p, q, d)    
        plain_text.append(plain_char)

    print ('Original Message: ', str)

    print ('Encrypted Message(UTF-8 Unicode characters) : ', end='')
    for element in cipher_text:
        print(element,end = '')

    print ('\nDecrypted Message: ', end='')
    for element in plain_text:
        print(element,end='')

def EncryptCharRSA(msg , p, q, d):
    n = p * q
    phi = (p-1) * (q-1)            
    cipher_no = 0
    cipher_char = ''

    for c in msg:
        # conver char to ascii for calculation
        cipher_no = (ord(c)** d) % n
        cipher_char = chr(cipher_no) 
        return cipher_char   
        #print (cipher_no)
        #plain_no = (cipher_no ** d) % n

def DecryptCharRSA(msg,p, q,d):
    n = p * q
    phi = (p-1) * (q-1)
    e = ModularMultiplicativeInverse(d,phi)
    for c in msg:
        plain_no = (ord(c) ** e) % n
        plain_char = chr(plain_no)
        return plain_char   

# Get modular multiplicative inverse
def ModularMultiplicativeInverse(d,n):
    i = 1
    while True:
        if (d * i) % n == 1:
         return i
        i = i + 1

if __name__ == '__main__' : main()
</code></pre>

<p>What you call <code>d</code> is actually <code>e</code> the public exponent and what you call <code>e</code> is actually <code>d</code> the private exponent. </p>

<p>Naming aside, your problem is that you're encrypting plaintext character code points that are larger than or equal to <code>n</code>. If they are, then you're actually encrypting not <code>ord("A")</code> (=65), but rather <code>ord("A") % n</code>. For small <code>n</code> as in your case this would lead to unrecoverable ciphertext:</p>

<pre><code>&gt;&gt;&gt; n = 3 * 17 # 51
&gt;&gt;&gt; ord("A")
65
&gt;&gt;&gt; ord("A") % n
14
</code></pre>

<p>And that is exactly that you would be able to decrypt. RSA is not something that can be used to encrypt arbitrarily big data. Normally, you would combine it with a secure and fast block cipher such as AES through <a href="https://en.wikipedia.org/wiki/Hybrid_cryptosystem" rel="nofollow">hybrid encryption</a>.</p>

python python-3.x cryptography rsa modular-arithmetic