[Course home page] [Course handouts]
YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 467b: Cryptography and Computer Security
 
Professor M. J. Fischer
Handout #6
February 10, 2005

Problem Set 2
Due in class on Thursday, February 17, 2005.

Problem 5:   Number theory review

Do the following number theory problems (a little bit mathematical):
  1. Express 1 as a linear combination of 2058 and 1019. What is 1019−1 modulo 2058?
  2. Calculate 2549 mod 29.
  3. Compute gcd(6188,4709).
  4. Show that 1234 and 357 are relatively prime. Find the multiplicative inverse of 357 in \Z1234.

Problem 6:   Number theory on computer

  1. Use Erathostenes's Sieve to count the exact number of primes less than one million. What is the estimate given by the Prime Number Theorem for this number? What is the relative error of the estimate?
  2. Get a ball-park figure of the time it takes to generate 1024-bit (308 decimal digits) and 2048-bit RSA keys on a modern PC by implementing RSA key generation using ln3 or any other big number package. Submit both the answer to this question and also the documented code that you wrote.

Problem 7:   RSA: Theory and Practice

Both mathematical and practical:
  1. (With pen) My toy RSA key is N=187, e=107. You observe a ciphertext c=5. What is the plaintext?
  2. (With computer) Consider this RSA key
    N
    :
    120457322460183418712065226069810172366048205604752299621042894
    397706979004293595855337673954215374262637794524272045818217908
    229478526584500478161639581465312338385782996541477205027111304
    594623121868092711384962797824273219760781441239953781771300913
    279928933475049007570476508440103847289002242478256388909.
    e
    :
    108320892662862955596302357470782070713553067937889499942447147
    355968656694359903462867764882012512073853365701549521606511348
    714104172770325051335157387268754815037274565436944534867153132
    292684133742464029214648540750182171588972138378036750055446438
    698076297078027248274182711872974326076429438507794270951.
    Suppose you manage to obtain the decryption key
    d
    :
    870778041505896784929057064247111975431088041103712624121674096
    250991494449208495397081617394569729997785285908978755792242047
    951504608606471891232362973145723219036260087876400092012690445
    506827289066083911176383869641400399764707038140971639114758576
    80395636175986539382761142627308502128595895319836883991.
    Factor N. (These numbers will be placed in the file /c/cs467/assignments/ps2/rsakeys.txt on the Zoo so that you don't need to copy them by hand.)



File translated from TEX by TTH, version 3.66.
On 22 Feb 2005, 19:15.