Write a python program to (a) Generate a pair of public and private keys for the

Question

Write a python program to (a) Generate a pair of public and private keys for the RSA scheme, where p and q each has n bits. (b) Given x = 2015, compute the encoded message y. (c) Given y computed above, compute the decoded message. Run your program for 3 different n values, report the results and the corresponding running time for each step (a), (b), and (c).

Explanation / Answer

"""Simple implementation of the RSA cryptosystem. This module is meant to show a simple and clear implementation of the RSA algorithm: http://en.wikipedia.org/wiki/RSA_(cryptosystem). It is meant to be readable, not fast. The usage is simple. First, create a random key pair: >>> public_key, private_key = make_key_pair(8) The number 8 is the _key length_. The higher this number, the stronger the encryption. The public key can be used to encrypt a message (in this module, a message is simply a positive integer number): >>> message = 5 >>> encrypted_message = public_key.encrypt(message) The encrypted information can be retrieved only with the private key: >>> private_key.decrypt(encrypted_message) 5 Private and public keys are made of three numeric parameters: ``n``, ``d`` and ``e``. ``n`` has the bit length specified with ``make_key_pair`` and is shared between the two keys; ``e`` is used by the public key encrypt; ``d`` is used by the private key to decrypt. It's worth noting that ``n - 2`` is the highest number that can be safely encrypted or decrypted. For example, encrypting (or decrypting) the number ``n - 1`` does nothing, and encrypting (or decrypting) the number ``n`` always returns 0. >>> key = PublicKey(n=143, e=113) >>> key.encrypt(142) # n - 1 142 >>> key.encrypt(143) # n 0 Also encrypting (or decrypting) 0 or 1 always returns 0 or 1: >>> key.encrypt(0) 0 >>> key.encrypt(1) 1 Note that sometimes the original and the encrypted messages are the same, as shown in the following example: >>> for x in range(143): # n ... if key.encrypt(x) == x: ... print(x) 0 1 12 21 34 44 65 66 77 78 99 109 122 131 142 """ import random from collections import namedtuple def get_primes(start, stop): """Return a list of prime numbers in ``range(start, stop)``.""" if start >= stop: return [] primes = [2] for n in range(3, stop + 1, 2): for p in primes: if n % p == 0: break else: primes.append(n) while primes and primes[0]

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.