Modern Cryptography Systems, Security Protocols, and Implementation

Cornell University Computer Science, Spring 1998

By Adi Fairbank

1. Week 1: General overview and search for references <http://www.rsa.com/rsalabs/newfaq>


1. Searched the RSA FAQ 3.0 on Cryptography for topics of interest, and good starting references.
2. Studied many modern public-key cryptosystems: RSA, DSA, Diffie-Hellman, Elliptic Curves.
3. Studied public-key concepts such as digital signatures, factoring algorithms, and one-way functions.


2. Week 2: Public-key cryptography <./paper_summaries/public_key.html>


1. Studied the paper, Digitalized Signatures and Public-Key Functions as Intractable as Factorization, by Michael O. Rabin. Rabin describes a public-key cryptosystem, and shows that cracking it is provably as difficult as factorization.
2. Studied more of the RSA FAQ 3.0. General cryptography concepts: block ciphers vs. stream ciphers, symmetric encryption vs. asymmetric encryption (public-key), cryptanalysis techniques.


3. Week 3: More public-key cryptography <./paper_summaries/public_key.html>


1. Studied the RSA paper, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, by Rivest, Shamir, and Adleman. This 1978 paper laid the foundation for the most powerful public-key cryptosystem in modern cryptography today. It describes a cryptosystem based on exponentiation modulo n, where n is a product of two large primes.
2. Studied the Diffie-Hellman paper, New Directions in Cryptography, by Whitfield Diffie and Martin E. Hellman. In addition to elaborating on general cryptography terms (block and stream ciphers) and describing possible cryptanalytic attacks on cryptosystems, they give a public-key cryptosystem based on discrete logarithms.


4. Week 4: Public-key cryptography additions and improvements – probabilistic cryptography <./paper_summaries/probabilistic_cryptography.html>
1. Studied the paper, An Efficient Probabilistic Public-Key Encryption Scheme Which Hides All Partial Information, by Manuel Blum and Shafi Goldwasser. Given a cryptographically strong pseudo-random bit generator, they show how to build a wrapper around public-key cryptosystems which eliminates all threats from known-plaintext attacks. The cryptanalyst cannot even obtain one block of plaintext from the ciphertext, hence the term "hides all partial information".
2. The idea of the Blum-Goldwasser algorithm is to use a randomly chosen seed to generate a random bit sequence and XOR it with the plaintext message. Send the random seed encrypted with the recipient’s public key along with the XOR result. The recipient then decrypts the random seed and can then generate the same random bit sequence, which can be XORed with the ciphertext to get the plaintext.


5. Week 5: Number Theory fundamentals and Elliptic Curve cryptography


1. Began reading the graduate mathematics textbook, A Course in Number Theory and Cryptography 2^nd ed., by Neal Koblitz. Studied divisibility and Euclidean algorithm for finding g.c.d. of two numbers. Studied number theoretic congruences.
2. Attempted to read Chapter VI of Koblitz’s textbook, but realized I wouldn’t understand any of it until I take a full Number Theory course.


6. Week 6: Miscellaneous security and cryptography techniques


1. Russel L. Brand’s paper, Problems with the Normal Use of Cryptography for Providing Security on Unclassified Networks describes many obstacles that the cryptographic community should deal with to make systems more secure. The main problems are short passwords, re-used passwords, broadcasting cleartext keys, and widespread misinformation about the cryptographic power of the cryptosystems out there currently.
2. Studied a paper on kerberos authentication by John T. Kohl: The use of Encryption in Kerberos for Network Authentication. The kerberos system authenticates individuals using a workstation connected to some network by maintaining a central database of private (DES) keys. When a user desires authentication, in order to communicate with another user, she can obtain a ticket from this central database (called a Key Distribution Center).
3. UNIX Password Security – Ten Years Later, by David C. Feldmeier and Philip R. Karn. The authors extensively outline all the problems with the Unix password system and the crypt algorithm. The main problems are easily guessed passwords and the publicly readable /etc/passwd file. Cryptanalysts can pre-encrypt large dictionaries using high-speed versions of the crypt algorithm, and compare the ciphertexts to the entries in /etc/passwd.


7. Week 7: Security protocols and implementations <http://www.apache-ssl.org> and <http://www.psy.uq.oz.au/~ftp/Crypto/>


1. Downloaded, compiled and installed a few commercial-strength secure web servers: Netscape Certificate Server and Apache-SSL. The Netscape server was pretty uneducational, but since the Apache server is open-source and free I was able to learn quite a bit about modern cryptographic software and transfer protocols (secure-http).
2. To get Apache working, I had to first install Eric A. Young’s Secure Sockets Layer (SSL) implementation. It was a library of all the modern cryptographic algorithms: DES, RSA, IDEA, RC5, etc.


8. Week 8: Public-key certificates and Certificate Authorities (CAs) <http://www.thawte.com> and <http://www.verisign.com>


1. After getting my secure web server working, I explored issues in making it actually secure. Due to the possibility of web site impersonation, complete web security requires authentication by a Certificate Authority. When you give a CA your public key, along with proof of your identity and ownership of your domain name and IP address, the CA digitally signs your public key and returns it to you for use. This is called a public-key certificate. It is like a verified identification document proving that you are who you say you are.
2. To learn the specifics behind public-key certificates, I generated an RSA key pair using Young’s SSL implementation, then sent it to Verisign. Since normally a server certificate costs about $500, I instead got a trial certificate for free.


9. Weeks 9 – 14: Implementation of RSA <./rsa_implementation>


1. I first had to write an infinite length arithmetic library in C. Then I used the pseudo-code algorithms given in the original RSA paper to implement a program which generates a key pair, encrypts, and decrypts blocks of text. The largest feasible key it can use is currently only 16 bits. This is because I used an unefficient way to generate primes, and to generate the public exponent from the private exponent. Generating a 24 bit RSA key pair takes a few minutes with my program, but encryption and decryption is still very fast.