SUNY Geneseo Department of Mathematics

Public Key Cryptography

Friday, December 3

INTD 105 17
Fall 2021
Prof. Doug Baldwin

Anything You Want to Talk About?

(No.)

SOFIs

SOFIs (“Student Opinion of Faculty Instruction” surveys) are now under way. You should have received an email with a link for filling them out.

Please do fill one out for this course, I really will read what you have to say, and act on it in future courses if possible.

Public Key Cryptography

Some History of Cryptography

Pre-1940

Cryptography is mostly a linguistic enterprise, i.e., mostly a matter of translating characters, words, or similar language elements between plaintext and ciphertext. For example, consider how using and breaking a code is approached in “The Gold Bug” or “The Beale Papers.”

Plaintext letters get encrypted with a key, ciphertext letters get decrypted with the same key

World War 2 to 1976

Thanks to the successes of Turing, Rejewski, and other mathematically-inclined World War 2 cryptanalysts, cryptography becomes a mathematical and computational enterprise.

Plaintext and ciphertext are viewed as sequences of numbers (computers represent characters as numbers anyhow), and the translations back and forth are thought of as mathematical or computational processes.

Plaintext numbers get encrypted with a key, ciphertext numbers get decrypted with the same key

1976

Whitfield Diffie and Martin Hellman propose “public key cryptography.” It seems like a clever theoretical idea with no practical realization.

Plaintext numbers get encrypted with a public key, ciphertext numbers get decrypted with a private key

If Alice wants to send a secret message to Bob, she encrypts it with his public key (which she and everyone else knows), and he can decrypt it with his private key (which only he knows):

Alice encrypting with Bob's public key, Bob decrypting with his own private key

Public key cryptography allows users to “sign” documents, i.e., prove authorship by encrypting in a way that only the author could do but that anyone can decrypt. In particular, Alice can sign a contract with Bob by encrypting it with her private key (which only she can do), and Bob, or a judge, or anyone else can verify that she signed it by checking that it is legible text when decrypted with her public key:

Alice encrypting with her own private key, Bob decrypting with Alice's public key

1978

Ronald Rivest, Adi Shamir, and Leonard Adelman demonstrate a practical public key cryptosystem (the so-called “RSA” system).

Rivest, Shamir, and Adelman also provide strong mathematical arguments, but not a proof, that their system is for practical purposes unbreakable. The arguments rest on the computational difficulty of factoring large numbers.

Post-1978

“Crypto-Wars”: National security types frantically try to suppress or regulate public key cryptography.

Internet commerce, crucially dependent on widely available, secure, and public-key cryptography, takes off.

The national security types mostly lose the crypto-wars (although they still try from time to time).

Cryptography becomes a ubiquitous enterprise, embedded in everyone’s cellphone, web browser, etc.

The RSA Cryptosystem

Still widely used as part, e.g., of secure web service.

Based on the idea of treating blocks of plaintext or ciphertext as very large numbers (“very large” meaning on the order of 300 to 500 digits long).

Key pairs are combinations of 3 numbers, usually called n, e, and d.

A public key is the pair (e,n).

The corresponding private key is the pair (d,n).

The main relationships between these numbers are…

n is the product of 2 large (i.e., 300 to 500 digits) prime numbers, p and q
d is any number that has no common factors with (p-1)(q-1). There are fast computer algorithms for finding such numbers if you know p and q.
e is a number such that the remainder of ed when divided by n is 1 (the so-called “multiplicative inverse modulo n of d”).

Now you can encrypt a plaintext message P to ciphertext C by

C = P^e mod n

and decrypt C by

P = C^d mod n

where “mod n” means the remainder after dividing by n.

Alice encrypts P as P to the E mod N, Bob decrypts C as C to the D mod N

Try it:

I suggested that the prime numbers to start with could be p = 5 and q = 11.
So n = pq is 55.
Then (p-1)(q-1) is 4×10, or 40
We arbitrarily picked d to be 7
With the help of a spreadsheet, we found that 23×7 is 161, and 161 / 40 has a remainder of 1, so e can be 23.

Then we tried encrypting the “message” 3: again with the help of a spreadsheet, we calculated that 3²⁷ mod 55 is 27

To decrypt 27, we used the spreadsheet to calculate 27⁷ mod 55, which turned out to be 3, i.e., the original plaintext.

Try RSA on a more realistic scale.

Next Lecture