Exam 2, MA 3203 Spring 2022
scheme | racket | prolog | function programming – 这个题目属于一个scheme的代写任务, 包括了scheme等方面
At the top of your exam, include your name and your M-number. Your reduced name is not used on this test.
It is assumed you will be using Mathematica or an equivalent calculator to perform many of these calculations. You may use the textbook, but no other information sources. You may discuss problems with other students in this class, or especially me, but you may not ask anyone to do your own problems.
Show your calculational steps, but also, be verbose and explain your reason- ing. This goes for all problems.
1.) Perhaps surprisingly at first glance, encryption with the DES keyK = 00 …0 can have a substantial effect on a text. Take your M-number and reduce it to its parities (i.e. odds become 1, evens become 0). Take the first 6 digits and repeat them twice to get a 12-bit plaintext. Using thesimplifiedmodel of DES from Section 4.2, do two rounds of encryption with keyK= 000000000. ExhibitL 2 R 2.
2.) (This question is not randomized. Use your own words.) Consider real (i.e. 64-bit block) DES. Show how it is possible for a change in any 1 bit of the plaintext to diffuse a potential change in bits throughout the entire 64-bit ciphertext.
3.) If your M-number is odd and ends in a last digit of 5, add 2. If your M- number is even, add 1, or 3 if adding 1 would result in a last digit of 5. If your M-number does not fall into either of these categories (i.e., it is not even, and not obviously divisible by 5), use it as is. Employ the Miller-Rabin test to determine whether the resulting number is composite or probably prime. Show your steps.
4.) Take the first two nonzero digits of your M-number to getk 1 , and the last two to getk 2. Use Mathematicas Prime[k] command to get theki-th primes. (Ifk 1 =k 2 , usek 1 andk 1 + 1.) Use these aspandq. Construct an RSA cryptosystem by calculatingnand(n), choosing an appropriatee, calculating d, and showing thatdis not vulnerable to the low-exponent attack. (Ifdis vulnerable, then youreis not appropriate!)
5.) Using the cryptosystem from question 4, encrypt the plaintext block with numerical value 63. Decrypt the ciphertext block with value 312. (Use these as numbers, not digits. For instance, this latter is three hundred twelve, not separately three, one, two.)
6.) As Eve, run a short plaintext attack against the ciphertext you got in the previous question for the plaintext 63.(You need not generate lists longer than 10 items. I strongly encourage the use of a symbolic calculator for the inversions, to prevent arithmetic errors.)
7.) If you get lucky with the quadratic sieve, you can find a singlexisuch thatx^2 iyi^2 (modn), withxi6yi(modn). In fact, ifnis a product of two odd primes – like an RSA number! – this isalwayspossible!
a.) Take yourn =pq from question 4 and find valuesxandysuch that n=x^2 y^2 = (x+y)(xy). Show thatx6y(modn), but that nevertheless x^2 y^2 (modn).(Hint: how is this related topandq?)
b.) Explain why this would always be possible albeit unlikely to be found by chance for an RSA numbern=pqwithpandqtwo large odd primes. Probably you just need to explain the thought process that gave you your answer to part a. It may be useful to observe that neitherpnorqcan be as big asn/2.
8.) (This question is not randomized. Use your own words to explain your response.)Alice and Bob, in remote places, wish to play a game of chance. They agree on the following scheme for drawing random numbers. (The numbers may be used in any fashion; perhaps the biggest wins.) Alice publishes an RSA cryptosystem (nA,eA). Alice uses some method of random number generation to produce two numbersx 1 andx 2 , which have not ever been used for this game before. She sends them to Bob, who picks one of them to be his,xB, and labels the other to bexAfor Alice, and tells Alice his choice. Alice decrypts the two numbers with her secret information to obtainyB=DA(xB) andyA=DA(xA), which she sends to Bob. They resolve their game withyAandyB.
Is this system secure in the sense of rules fairness? That is, could either Alice or Bob force a win for themselves in some way? Can both parties verify the results? Ignore the possibility of interference from Eve, assume neither party quits early, and assume cracking Alice RSA system is difficult for Bob.