Scribd
Upload
3 views

Vertopal.com Assignment

Uploaded by

mr.breefcos2000
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
3 views

Vertopal.com Assignment

Uploaded by

mr.breefcos2000
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

Public Key Cryptograpy with RSA algorithm

(simplified version)
Key generation
• Pick any two prime numbers namely p and q
• Calculate n=p q. Here n is called the modulus.
• Calculate ϕ ( n )= ( p − 1 )( q − 1 ).
• Choose 1<e <ϕ ( n ) such that e and ϕ ( n ) are coprime. Here e is called the exponent.
• Find 1<d <n such that e d ≡ 1(mod ϕ ( n ) ). Here d is called the private key.

Key distribution
• The modulus and the exponent are called the public key. They are used to encrypt any
message. So distribute them.
• The modulus and the private key are used to decrypt the encrypted message. So keep
secret.

Encryption & Decryption


• To encrypt a number x , use the following formula:
y ≡ x e (mod n)
• To decrypt encrypted y use the following formula:
x ≡ y d ( mod n)
Example
Some of theese steps in key generation requires high level of mathematics and beyond the
scope of this lesson. So in this assinment they are given precalculated.

Let n=3 ×11=33 , e=3 and d=7.

Actually this keys are not secure because the strength of RSA algorithm lies behind the
calculation difficulty of d from n and e only. And this is not possinle when the number n is not
large enought.

For example to encrypt the number x=20 using the public key e=3 , you need to calculate

y ≡203 ≡14 (mod 33)


And to decrypt the number y=14 using the private key d=7, you need to calculate

x ≡ 147 ≡20 (mod 33)

Implementation
1. Complete the implementation of encryption and decryption functions in Python.
2. Find different public and private keys and test your implementation with these keys.
3. Try to implement the key generation process. What are the difficulties?
def encrypt(x, n=33, e=3):
return pow(x, e, n)

def decrypt(y, d=7, n=33):


return pow(y, d, n)

The following assertions must not raise an exception.

assert 18 == decrypt(encrypt(18))
public_key, private_key = generate_keys()
print("Public key:", public_key)
print("Private key:", private_key)

x = 18
y = encrypt(x, public_key[0], public_key[1])
print("Encrypted: ", y)

z = decrypt(y, private_key[1], private_key[0])


print("Decrypted:", z)

assert z == x

def encrypt(x, n=33, e=3):


return (x ** e) % n

def decrypt(y, d=7, n=33):


return (y ** d) % n

assert 18 == decrypt(encrypt(18))

import random

def generate_keys():

p = random.randint(1, 100)
q = random.randint(1, 100)
while not (is_prime(p) and is_prime(q)):
p = random.randint(1, 100)
q = random.randint(1, 100)

n = p * q
phi_n = (p - 1) * (q - 1)

e = random.randint(1, phi_n)
while gcd(e, phi_n) != 1:
e = random.randint(1, phi_n)

d = pow(e, -1, phi_n)

return n, e, d

def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True

def gcd(a, b):


while b != a:
a, b = b, a % b
return a

n, e, d = generate_keys()
assert 18 == decrypt(encrypt(18, n, e), d, n)

You might also like