Problems Goal The purpose of this project is to implement the RSA public-key cryptosystem. The RSA (Rivest-Shamir-Adlema

Post by **answerhappygod** » Fri Jul 08, 2022 7:26 am

: Problems Goal The Purpose Of This Project Is To Implement The Rsa Public Key Cryptosystem The Rsa Rivest Shamir Adlema 1 (98.72 KiB) Viewed 44 times

Problems Goal The purpose of this project is to implement the RSA public-key cryptosystem. The RSA (Rivest-Shamir-Adleman) cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and operating systems. It works by manipulating integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate huge integers (hundreds of digits), which is naturally supported by the int data type in Python. Your task is to implement a library that supports core functions needed for developing the RSA cryptosystem, and implement programs for encrypting and decrypting messages using RSA. The RSA Cryptosystem The RSA public-key cryptosystem involves three integers n, e, and d that satisfy certain math- ematical properties. The public key (n, e) is made public on the Internet, while the private key (n, d) is only known to Bob. If Alice wants to send Bob a message a € [0, n), she encrypts it using the function E(x)= x mod n, where n = pq for two distinct large prime numbers p and q chosen at random, and e is a random prime number less than m= (p-1)(q-1) such that e does not divide m. For example, suppose p = 47 and q = 79. Then n = 3713 and m = 3588. Further suppose e = 7. If Alice wants to send the message r = 2020 to Bob, she encrypts it as E(2020) = 20207 mod 3713 = 516. When Bob receives the encrypted message y = E(x), he decrypts it using the function D(y) = yd mod n, where d = [1, m) is the multiplicative inverse of e mod m, ie, d is an integer that satisfies the equation ed mod m = 1. Continuing the example above, if d = 2563, then when Bob receives the encrypted message y = 516 from Alice, he decrypts it to recover the original message as
• decrypt (y, n, d) - Implement the function D(y) = yª mod n. • primes (lo, hi) Create an empty list. For each pe [lo, hi), if p is a prime, add p to the list. Return the list. _sample (a, k) - - Create a list b that is a copy (not an alias) of a. Shuffle the first k elements of b. Return a list containing the first k elements of b. - choice(a) Get a random number r € [0,1), where I is the number of elements in a. Return the element in a at the index r.
keygen (lo, hi) Get a list of primes from the interval [lo, hi). Sample two distinct random primes p and q from that list. Set n and m to pq and (p-1)(g- 1), respectively. Get a list primes from the interval [2, m). Choose a random prime e from the list such that e does not divide m (you will need a loop for this). Find a de [1,m) such that ed mod m = 1 (you will need a loop for this). Return the tuple¹ (n,e,d). encrypt (x, n, e) Project 4 (RSA Cryptosystem) Implement the function E(x) = xe mod n. decrypt (y, n, d) - Implement the function D(y) = y mod n. • primes (lo, hi) Create an empty list.
Problem 1. (RSA Library) Implement a library called rsa.py that provides functions needed for developing the RSA cryp- tosystem. The library must support the following API: тва keygen (lo, hi) encrypt (x, n, e) decrypt (y, n, d) bitLength (n) dec2bin(n, width) bin2dec (n) generates and returns the public/private keys as a tuple (n, e, d), picking prime numbers p and q needed to generate the keys from the interval [1o, hi) Directions: encryptsx (int) using the public key (n, e) and returns the encrypted value decrypts y (int) using the private key (n, d) and returns the decrypted value returns the least number of bits needed to represent n returns the binary representation of n expressed in decimal, having the given width and padded with leading zeros returns the decimal representation of n expressed in binary > "/workspace/project4 $ python3 rsa.py S encrypt (S) = 1743 decrypt (1743) =S bitLength (83) = 7 dec2bin (83) # 1010011 bin2dec (1010011) 83
Eile Eclit View Navigate Code Befactor Run Iools VCS Window Help project4) sa.py ✪ I + ✓ project4 sources clata decrypt.py distance.py encrypt.py 5 keygen.py 6 palindrome.py 7 8 9 10 11 project4.pdf report.txt reverse.py sa py setup.cfg sin.py transpose.py > External Libraries ✓ Scratches Runc 12 13 14 Scratches and Com 15 scratch.py 1 2 scratch X 3 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 50 51 52 53 54 55 palindrome.py X scratch.py x keygen.py X X un import stdio import stdrandom import sys def keygen (lo, hi): A D project4-rsa.py Generates and returns the public/private keys as a tuple (n, e, d). Prime numbers p and q #needed to generate the keys are picked from the interval [lo, hi). A ➡ encrypt.py X # Encrypts x (int) using the public key (n, e) and returns the encrypted value. def encrypt(x, n, e): # Decrypts y (int) using the private key (n, d) and returns the decrypted value. def decrypt(y, n, g): decrypt.py X distance.py X # Returns the least number of bits needed to represent n. def bitLength (n): ệ return len(bin(n)) - 2 # Returns the decimal representation of n expressed in binary. Edef bin2dec (n): 4 return int(n. 2) ... #Returns the binary representation of n expressed in decimal, having the given width, and padded # with leading zeros. def dec2bin(n, width): 4 return format(n, ¹0%db' % (width)) # Returns a list of primes from the interval [lo, hi). def primes (lo, hi): A sin.py x transpose X # Returns a random item from the list a. def _choice(a): A # Unit tests the library [DO NOT EDIT). Edef main(): x = ord(sys.argv[1]) reverse.py X # Returns a list containing a random sample (without replacement) of k items from the list a. def sample(a, k): A Version Control Python Packages TODO Python Console Problems Terminal Services Download pre-built shared indexes: Reduce the indexing time and CPU load with pre-built Python packages shared indexes // Always download // Download once // Do... (loday 3:47 PM scratch transpose.py X 0 Q. X [Sady X rsa.Dy 01 A 2 A 19 2^ v 0 6:18 LF UTF-8 4 spaces Python 3.10
Eile Eclit View Navigate Code Befactor Run Iools VCS Window Help project4) sa.py ✓ project4 sources I clata decrypt.py distance.py encrypt.py 24 keygen.py 25 palindrome.py 26 project4.pdf 27 28 report.txt reverse.py 29 farhs.py 30 31 32 33 setup.cfg sin.py transpose.py > External Libraries Scratches and Con 34 ✓ Scratches scratch.py 36 35 37 21 22 23 Runc scratch X 38 39 40 41 42 42 42 43 44 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 palindrome.py X scratch.py Xkeygen.py X # Returns the least number of bits needed to represent n. def bitLength(n): A return len(bin(n)) - 2 project4-rsa.py # Returns the decimal representation of n expressed in binary. Edef bin2dec (n): A return int(n, 2) encrypt.py X decrypt.py X # Returns a list of primes from the interval [lo, hi). def primes (lo, hi): e ... #Returns the binary representation of n expressed in decimal, having the given width, and padded # with leading zeros. def dec2bin(n, width): A return format(n, ¹0%db' % (width)) # Returns a random item from the list a. def _choice(a): P S # Returns a list containing a random sample (without replacement) of k items from the list a. def _sample(a, k): Q # Unit tests the library [DO NOT EDIT]. Edef main(): x = ord(sys.argv[1]) ned keygen (25, 100) M encrypted = encrypt(x, n. e) WOLPE stdio.writef('encrypt (%c) = %d\n', x, encrypted) decrypted decrypt(encrypted, nd) stdio.writef('decrypt (%d) = %c\n', encrypted, decrypted) vetype distance.py X width= bitLength(x) stdio.writef('bitLength ( %d) = %d\n', x, width) xBinary dec2bin(x, width) if __name__ == '__main__4 _main() sin.py x stdio.writef('dec2bin (%d) = %s\n', x, xBinary) A stdio.writef('bin2dec (%s) = %d\n', xBinary, bin2dec (xBinary)) reverse.py X transpose X TODO Python Console. O Problems Services Version Control Run Python Packages Terminal Download pre-built shared indexes: Reduce the indexing time and CPU load with pre-built Python packages shared indexes // Always download // Download once // Do... (loday 3:47 PM scratch 0 GQ ✶ transpose.py X rsa.Dy py X 01 A 2 A 19 2 ✪ X 6:18 LF UTF-8 4 spaces Python 3.10