辅导MAT-LCT、python编程调试、讲解Python语言、辅导decrypts messages
解析Haskell程序|辅导留学生 St
MAT-LCT Final computer project : RSA
Goal
You will create a program in python which encrypts and decrypts messages using RSA two letters
at a time. For this version of the project, you need to work on your own.
Help!
To get you started, I created a file Help.py which you can download on omnivox. Download it into
the same directory as your project and start your program with the line.
from Help import *
You will therefore have access to the following functions.
P rime(a) which returns true or false depending on whether a is prime or not.
ListP rime(small, big) which takes in two integers small and big and lists all the primes
between them.
quotient(a, d) which takes two positive integers and returns (q, r) where a = qd + r gives the
quotient and the remainder of division of a by d.
mod(a, d) which takes two positive integers and returns r the remainder when a is divided by
d.
quot(a, d) which takes two positive integers and returns q the quotient when a is divided by
d.
Euclidean(a, b) which takes in two positive integers and returns (d, s, t) the greatest common
divisor d of a and b as well as the coefficients s, t in d = sa + tb.
RelativelyP rime(a, b)which takes in two integers a, b and returns true if a, b are relatively
prime and false otherwise.
Inverse(a, n) which returns the inverse of a modulo n if such an inverse exists. Otherwise it
returns False.
P owerMod(x, e, n) which returns x
e modulo n in an efficient way.
It also contains two dictionaries.
Letter. Which pairs each number with its corresponding letter. For example Letter[1] would
return A. Letter[0] gives a space.
Number. Which pairs any letter, lowercase or uppercase with its number. For example both
] would return 1.1 Setting up RSA : 20%
1. Build a function P ickP rimes() which returns two primes chosen by the user.
Ask the user for the minimum m and the maximum M value for the primes.
List all primes between m and M using ListP rimes(m, M).
Ask the user to pick two primes p, q.
Check that the chosen integers p, q are really different and are really primes.
Return (p, q).
2. Build a function SetU p(). It will return the modulo n, the power e and d the inverse modulo
(n) of this power.
Ask the user if they will use random primes or select primes themselves.
Choose p, q according to the user’s preferences.
Check that p, q are at least 2627 so that we can encrypt using two-letter blocks.
Compute n and (n).
Ask the user to pick a power e.
Check that e is relatively prime to (n).
Find the inverse d of e modulo (n).
Return (n, e, d).
3. Build a function RandomP ickP rimes(min, max) which selects two random primes between
min and max.
Build a list of all primes between min and max using ListP rimes(min, max).
Randomly pick two primes p, q from this list using “random.randint(a, b)” to pick a
position in ListP rime(min, max).
Check that the chosen integers p, q are really different.
Return (p, q).
4. Build a function SetU pRandom(min, max). It will return the modulo n, the power e and d
the inverse modulo (n) of this power.
Choose p, q using RadomPickPrimes(min,max)
Check that p, q are at least 2627 so that we can encrypt using two-letter blocks. Compute n and (n).
Pick e a random prime between 3 and 100.
Check that e is relatively prime to (n).
Find the inverse d of e modulo (n).
Return (n, e, d).2 Encoding messages : 20%
1. Build a function GetMessage() with no input. It should output a list of letters which contains
the message.
Create an empty list Message.
Repeatedly ask the user for the next letter and add that letter to Message.
Stop when the user enters 1.
If there is an odd number of letters in Message, add a blank space.
Return Message.
2. Build a function LetterT oNumber(Message) with input Message, a list of letters. It will
return the equivalent of the message in numbers.
Create a new blank list MessageInNumber
For each letter in Message, add the corresponding number to MessageInNumber using
the dictionary Number.
return MessageInNumber
3. Build a function Encode(Message, n, e) with input Message, a list of letters, n the modulo
and e the power. It returns the encrypted message as a list of integers.
Using LetterT oNumber, transform the message into InNumber a list of numbers.
Create a new empty list Coded.
While InNumber is not empty.
x = the next element of InNumber. (Use the command pop(0) on that list.)
y = the next element of InNumber. (Use the command pop(0) on that list.)
NumberT oEncrypt = 100x + y
Add NumberT oEncrypte mod n to Coded Use the function pow to compute this power.
return Coded
3 Decoding messages : 20%
1. Build a function GetMessageNumber().
Input. None
Output. A list of numbers to decrypt given by the user.
2. Build a function NumberT oLetter(Message).
Input : Message, a list of numbers between 0 and 26.
Output : A list of the corresponding letters.
3. Build a function Decode(Message, n, d).
Input. Message, a list of numbers, n the modulo and d the private key.
Output. Returns the decrypted message as a list of letters.4 Core : 10%
Set up the RSA encryption for the first time (use SetUp()).
Offer the following options to the user.
– Set up RSA again.
– Encrypt a message.
– Decrypt a message
– Print the public key (n, e).
– Print the private key d.
– Leave.
Follow the choice. Loop back until the user asks to leave.
Marking scheme
Here is how your grade will be computed.
SetUp of RSA : 20 %.
Encoding messages using RSA : 20%.
Decoding messages using RSA: 20 %.
Core : 10 %.
Comments : 10 %.
Quality of the interaction with the user : 10%.
– Are your instruction clear and to the point?
– Are you using complete sentences and appropriate return of line?
– Are you answering clearly the request of the user ?
– Are your answers given in a nice readable format?
Robustess of the program : 10%.
– Does your program collapse when the user enters an integer when a letter is required?
– Does your program collapse when the user enters a string when a integer is required?
– Et cetera.