RSA-based Encryption and Digital Signature Schemes

\( \def\ZZ{\mathbb{Z}} \def\GG{\mathbb{G}} \def\HH{\mathbb{H}} \)

Your Task

In this lab, you will write rsa.py.

GCD and Modular Multiplicative Inverse

You will often need to use compute the GCD of the two numbers. You can use math package.
```
>>> from math import gcd
>>> gcd(6, 35)
1
>>> gcd(15, 35)
5
>>> gcd(60, 72)
12
```
You will need to compute the modular inverse. In Python, you can compute \(a^{-1} \bmod m\) by using expression pow(a, -1, m).
```
>>> pow(3, -1, 7)
5
>>> 3*5 % 7
1
```

[10pts] Part 1: Checking if a RSA Encryption Key is Valid

Write a function is_e_good(e, p, q) in rsa.py that checks if the public key e is good.

Sample Run

This example is from the homework.


>>> p = 3
>>> q = 5
>>> from rsa import *
>>> for e in range(2, p*q):
...   if is_e_good(e, p, q): print(e, "is good")
...
3 is good
5 is good
7 is good
9 is good
11 is good
13 is good

[10pts] Part 2: Computing the RSA decryption Key

Write a function compute_d(e, p, q) in rsa.py that computes the secret key d from (e, p, q).

Sample Run


>>> from rsa import *
>>> p = 3
>>> q = 5
>>> for e in range(2, p*q):
...   if is_e_good(e, p, q):
...      d = compute_d(e, p, q)
...      print("e=", e, " , d=", d)
...
e= 3 ,  d= 3
e= 5 ,  d= 5
e= 7 ,  d= 7
e= 9 ,  d= 1
e= 11 ,  d= 3
e= 13 ,  d= 5

[15pts] Part 3: Key Generation

Write a function gen() in rsa.py that implements the RSA key generation algorithm. The box below provides partial code, and fill the rest as necessary. You may want to check out the documentation.


from Cryptodome.Util.number import getPrime 
from Cryptodome.Random.random import randrange
def gen(bit_len):
  p = getPrime(bit_len//2)
  q = getPrime(bit_len//2)
  
  # ... fill the code ...

  pk = (n, e)
  sk = (n, d)
  return (pk, sk)

Sample Run

The numbers you see will be different since gen() generates a random key pair.


>>> from rsa import *
>>> pk, sk = gen(30)
>>> pk
(417820859, 76516999)
>>> sk
(417820859, 149906119)
>>> pk, sk = gen(128)
>>> pk
(290811551835070190548173514535831587391, 270485843771875936504095435141447615209)
>>> sk
(290811551835070190548173514535831587391, 112639414460916485729877867067724462489)

[25pts] Part 4: Encryption and Decryption

Add the following four functions in rsa.py:

enc(), dec(),
  dec_oaep(), enc_oaep()

Functions enc and dec: These functions implement the PlainRSA encryption/decryption algorithms. Give an integer object for the message or ciphertext.


>>> from rsa import *
>>> pk = (314585159924566279413389006096834903593, 287166174272030546048198787100648860393)
>>> sk = (314585159924566279413389006096834903593, 313651388307762499391622896983743514657)
>>> m = 12345678901234567890
>>> enc(pk, m)
192854617720361680378999294429127284047
>>> c = 192854617720361680378999294429127284047
>>> dec(sk, c)
12345678901234567890
>>> pk, sk = gen(200)
>>> dec(sk, enc(pk, m))
12345678901234567890

Function dec_oaep(n, e, d, c) that implements the RSA-OAEP decryption. Here, (n, e, d) are integers but c must be a bytes type object.

Note: Refer to the documents below for using the relevant packages of Cryptodome. As you did in the project, replace Crypto.??? in the documentation with Cryptodome.???

RSA package. Use function construct to create a RSAKey object properly.
RSA OAEP package.
Usually, (u, d) is the secret key, but RSAKey additionally needs e. Therefore, instead of using sK directly, the function takes (n, e, d) as the decryption key.

Sample run:


>>> from rsa import *
>>> n= 1598371663032307392581317159018956557413746789905305182544778875820652618827181558764550329306704455598319881191970781701
>>> e= 957306016268192234483842550692726962224542352641043375139141224011896959430604883780056957621723415435116210799395956395
>>> d= 650984565456181075067519006385779243027188506477102924425498717896526779130041487568652696142066808779222267335440018727
>>> c= b"\x04*u\xc3\xf6gst+\xe7\xe8\xe0\x96\xd1]\x17s\xbe\x1e\xf6~B'\xe8\x9f:\x97\x9cqF\xa3Nek\xcf-X\x08\xa9R\xbf\xb7\xf0\x8c\xaa\x00\x8e$=\xc5"
>>> m1 = dec_oaep(n, e, d, c)
>>> m1
b'Go'

enc_oaep(pk, m): This function implements the RSA_OAEP encryption algorithm. The input message m must be of the bytes type. Note: Since OAEP is a CCA secure algorithm, modifying the ciphertxt will cause the Cryptodome OAEP-decryption function to raise an exception. In that case, dec_oaep() should print the error as follows:

OAEP: decrpytion error!

Also, the function dec_oaep should return b"".

Test code test_part4.py should output the following:

$ python3 test_part4.py
m = 12345678901234567890
enc(pk, m): 690936668198903..(omitted)..3814952490198
dec(sk, c): 12345678901234567890
pk1, sk1 = gen(200)
dec(sk1, enc(pk1, m)): 12345678901234567890

n= 713184925..(omitted)..85909482241
e= 607506876..(omitted)..09826486091
d= 353241543..(omitted)..38653642259

dec_oaep(n, e, d, c)= b'hello'
modifying the last byte of c into c1...
OAEP: decryption error!
dec_oaep(n, e, d, c1)= b''

[15pts] Part 5: Full Domain Hash -- Verifying a signature

Write a function verify(pk, bytes_data, signature) that performs the verification of Full Domain Hash.

Download: pcap.tar.

Sample Run

Read the following sample run carefully.

Use SHA-256 for the hash function. The hash should be 256 bits long, which amounts to 32 bytes. Convert the bytes into a number using the big endian system.
Make sure to print out the hash values correctly in the function verify.
The function should return True or False.


  >>> from rsa import *
>>> pk = (1034347805468283269827508936486170888522287052492910727094077050318809053334171091720678869, 
510877216672959214128776340810554985688514636215490153898356945128401661157079729351949307)
>>> D = open("pcap.tar", "rb").read()
>>> sig = 712827146594771643203555365704210706658776126768689151938275544697784235891977989236268064
>>> verify(pk, D, sig)
Hash of the data (bytes):  b"\xf6\x16\xdan\x0b\xf7\xfe\xe0\xc1\xe3Hz\xc9\xaeg)\xe6'/nI\xc4\x91\x8e\xc3\xc9\xbf\xdbl\xd8#5"
Hash of the data (number):  111309338934466844412421473807411338124723784588157710110020410251474569274165
True
>>> sig -= 1
>>> verify(pk, D, sig)
Hash of the data (bytes):  b"\xf6\x16\xdan\x0b\xf7\xfe\xe0\xc1\xe3Hz\xc9\xaeg)\xe6'/nI\xc4\x91\x8e\xc3\xc9\xbf\xdbl\xd8#5"
Hash of the data (number):  111309338934466844412421473807411338124723784588157710110020410251474569274165
False

[15pts] Part 6: Full Domain Hash -- Signing a message

Write a function sign(sk, bytes_data) that outputs the signature on the bytes_data using the secret key sk.

Sample Run


>>> from rsa import *
>>> sk = (1034347805468283269827508936486170888522287052492910727094077050318809053334171091720678869, 
538046828872107393782134652951416777717550347945260104579354655057630363967157872764116723)
>>> D = open("pcap.tar", "rb").read()
>>> sign(sk, D)
712827146594771643203555365704210706658776126768689151938275544697784235891977989236268064
>>> pk, sk = gen(500)
>>> verify(pk, D, sign(sk, D))
Hash of the data (bytes):  b"\xf6\x16\xdan\x0b\xf7\xfe\xe0\xc1\xe3Hz\xc9\xaeg)\xe6'/nI\xc4\x91\x8e\xc3\xc9\xbf\xdbl\xd8#5"
Hash of the data (number):  111309338934466844412421473807411338124723784588157710110020410251474569274165
True
>>> pk[0].bit_length() >= 450
True

[10pts] Part 7: Lab Report and Submission

Write a lab report by using the provided template. The writing quality of the lab report matters.

Deliverables

For each part, give a sample run in your lab report.
rsa.py

~/bin/submit -c=IT430 -p=lab10 rsa.py lab10_report.docx