RSA (Rivest, Shamir, Adleman)

asymmetric key cryptosystem/ public key cryptosystem

can be used for both encryption/decryption and authentication; in RSA we use the sender’s private key to sign the message and the recipient’s public key to encrypt the message.

the security of the RSA cryptosystem resides in the hardness/time consuming problem of factoring a large number (the public modulus m) into its two prime factors (private primes p and q). Factoring integers is much harder than multiplying them!

p=999999599;
q=9999999967;
m=p*q;

Timing[p*q]
Timing[FactorInteger[m]]

p=2425967623052370772757633156976982469681;
q=5570373270183181665098052481109678989411;
m=p*q;

Timing[p*q]
Timing[FactorInteger[m]]

The largest known prime number as of January 2017 is (2^74207281)-1, a number with 22,338,618 decimal digits. RSA protocols usually use a 2048-bit modulus m (which corresponds to 617 decimal digits).

Mathematics behind RSA

RSA is based on Euler’s Theorem. Let p and q be two distinct prime numbers. Let m=pq.

If a is relatively prime to m, then (a^((p-1)(q-1)))≡1(mod m).

If a is any integer (not necessarily relatively prime to m), and k is any positive integer, then

(a^(k(p-1)(q-1)+1))≡a(mod m).

This is a particular case of the general form of Euler’s Theorem which says that is m is any positive integer, and a is relatively prime to m, then (a^(ϕ(m)))≡1(mod m), where ϕ is Euler’s totient function.

RSA Setup

Alice selects two distinct primes p and q and computes m=pq and n=(p-1)(q-1).

She chooses a number e, relatively prime to n=(p-1)(q-1), and finds the multiplicative inverse of e modulo n, that is, she finds an integer d such that ed≡1(mod n).

Alice makes (m,e) public. m is called the public modulus, and e the public key or the encryption key.

Alice keeps p,q,n,d a secret. d is called the private key or the decryption key.

Encryption function:  E(x)=(x^e)(mod m), where 1≤x≤m-1.

Decryption function: D(y)=(y^d)(mod m), where 1≤y≤m-1.

Example

Alice sets up an RSA scheme

select primes p=11 and q=3.

compute m=pq=33 and n=(p-1)(q-1)=(11-1)(3-1)=20

choose a number e, relatively prime to n=20. Suppose we choose e=3.

find an integer d such that ed≡1(mod 20). The integer d is the multiplicative inverse of e, modulo 20. In this case, d=(e^(-1))(mod 20)=(3^(-1))(mod 20)=7 (mod 20).

public key (m,e)=(33,3)

e=3 is the public encryption key.

m=33 is the public modulus.

private key (p,q, n,d)=(11,3,20,7).

d=7 is the private decryption key.

Bob wants to send the message x=14 to Alice.

encrypt the message x=14 using Alice’s public key.

compute y=(x^e)(mod m)=(14^3)(mod 33)=2744 (mod 33)=5 (mod 33).

the ciphertext is y=5.

Bob sends the ciphertext y=5 to Alice.

Alice receives the ciphertext y=5 (from Bob?)

use the private key d=7 to decrypt it.

compute x=(y^d)(mod m)=(5^7)(mod 33).

x=(5^7)(mod 33)=((((5^3)))^2)*5  (mod 33)=(125^2)*5=(((-7))^2)*5=7*2=14 (mod 33)

the decrypted message is x=14. (This is exactly Bob’s unencrypted message!)

RSA with Mathematica

EncryptionRSA[x_ ?IntegerQ, e_ ?IntegerQ,  m_ ?IntegerQ]:= PowerMod[x,e,m]
SetAttributes[EncryptionRSA, Listable]

DecryptionRSA[x_ ?IntegerQ,  d_ ?IntegerQ,  m_ ?IntegerQ]:= PowerMod[x,d,m]
SetAttributes[DecryptionRSA, Listable]

To decrypt the cipher message y = 5 received from Bob, Alice computes :

DecryptionRSA[5,7,33]

To decrypt a list of cipher messages, say {5, 17, 10} received from Bob, Alice computes:

DecryptionRSA[{5, 17, 10},7,33]

Short exercise: Produce a table with the encryptions of all integers between 0 and 32. How many unconcealed messages are there?

Solution:

T=Table[i->EncryptionRSA[i, 3, 33],{i,0,32}]

Unconcealed Messages:

All 33 values of x (from 0 to 32) map to unique ciphertext values y in the same range, in a sort of random manner.

There are 9 values of x that map to themselves, 0,1,10,11,12, 21, 22, 23, 32! These are called unconcealed messages. The numbers 0,1,m-1 are no surprise, because they always map to themselves under the map (x^e) (mod m). To see how many unconcealed messages there are for a chosen pair (m,e), we must solve a modular equation (x^e)≡ x (mod m), or equivalently (x^d)≡ x (mod m). In this case one solves (x^3)≡ x (mod 33), which is equivalent to x(x-1)(x+1)≡ 0 (mod 33).

Solve[x^3==x, x, Modulus->33]

Theorem: Let m = pq be the product of two distinct prime numbers,  and suppose that e is relatively prime to (p-1)(q-1). Then the number of elements x in (Subscript[ℤ, m]) that satisfy the relation (x^e)=x (mod m) is given by (GCD[e-1,p-1]+1)(GCD[e-1,q-1]+1).

p=3;q=11;e=3;
(GCD[e-1,p-1]+1)(GCD[e-1,q-1]+1)

Since p - 1, q - 1, e - 1 are all even, the number of unconcealed messages for any modulus m  is at least 9. In practice, the encryption exponent e is small, whereas p and q are quite large, so the number of unconcealed messages will be very small compared to the total number of possible messages.

Symmetric vs Asymmetric key Cryptography

Symmetric Key Cryptography

same key used for encryption/decryption

fast encryption/decryption

key exchange - a big problem!

used mainly for encryption/decryption, not so much for digital signatures

Asymmetric Key Cryptography

one key (public) used for encryption, another key (private) used for decryption

slower encryption/decryption

key exchange - no problem at all!

can be used for encryption/decryption, as well as for digital signatures

SSL (Secure Sockets Layer),  TLS (Transport Layer Security)
Handshake Protocol

Several versions of the protocols are in widespread use in applications such as web browsing, email, Internet faxing, Instant messaging, and voice - over - IP (VoIP). Major web sites (including Google, YouTube, Facebook and many others) use TLS to secure all communications between their servers and web browsers.

provides security and privacy over the Internet by using encryption and server/client authentication based on RSA.

the SSL protocol negotiates encryption keys, as well as authenticates the server before data is exchanged by the higher level applications.

HTTP (Hypertext Transfer Protocol) and FTP (File Transfer Protocol) can be layered on top of SSL

⟹ HTTPS (Hypertext Transfer Protocol Secure).

HTTPS is especially important over unencrypted wifi networks where anyone on the same local network can eavesdrop (packet sniffing) and discover sensitive information.

HTTPS provides a guarantee that one is communicating with precisely the web site/ web server that one intended to communicate with, as well as ensuring that the messages between the user and the site cannot be forged by any third party.

SSL Handshake protocol has two parts

server authentication (based on RSA).

(optional) client authentication (RSA).

Part 1

The handshake protocol begins when a client connects to a TLS or SSL-enabled server requesting a secure connection and presents a list of supported symmetric key ciphers (DES, Triple DES, AES, IDEA, MD5, RC2, RC4, etc.).

the server, in response to a client’s request, sends its digital certificate (server name, trusted certificate authority, public RSA key) and its symmetric key cipher method preference.

the client generates a master key k, which he/she/it encrypts with the server’s public key using RSA, and transmits the encrypted master key to the server.

the server decrypts (recovers) the master key k, using his RSA private decryption key.

the server authenticates itself to the client by returning a message signed with his private RSA key and encrypted with the symmetric cipher with key k.

subsequent data is encrypted with the symmetric key cipher and with keys derived from the master key k.

Part 2 (optional)

the server sends a challenge to the client

the client authenticates itself to the server by returning the client’s digital signature on the challenge, as well as its public-key certificate.

Electronic commerce

IKP (Internet Keyed Payment Protocol)

secure payments involving three or more parties; a buyer and a seller interact with a third party “acquirer” such as a credit card system or a bank, to authorize transactions.

SET (Secure Electronic Transaction Protocol)

secure, cost effective bankcard transactions over open networks, implemented by VISA, MasterCard, etc.

SET includes protocols for purchasing goods and services electronically, requesting authorization of payment and requesting “credentials” (digital certificates) binding public keys to identities.

SET supports DES for bulk data encryption and RSA for signatures and public-key encryption of the DES encryption keys and bankcard numbers.

Digital signatures with RSA

Evil Third Party

Eve wants to impersonate Bob. She writes a message x=”Alice, I don’t like you, Sincerely Bob”, Encrypts x using Alice’s public key y= (x^e)(mod m), and send y to Alice. Alice decrypts the message y using her private key d, reads the message, but she has no way of verifying if the sender was really Bob.

Alice and Bob

Bob would like to send Alice the following message x=”Alice, I like you, Sincerely Bob”. He would like to send Alice the message x, and also affix a digital signature to confirm his identity. This will be called a message-signature pair.

Alice has her RSA scheme: public modulus (Subscript[m, A])=(Subscript[p, A])*(Subscript[q, A]), public encryption key (Subscript[e, A]), private decryption key (Subscript[d, A]).

Bob

Bob sets up his own RSA scheme: public modulus (Subscript[m, B])=(Subscript[p, B])*(Subscript[q, B]), public encryption key (Subscript[e, B]), private decryption key (Subscript[d, B]).

Bob signs the message x with his own private RSA key. The signature is σ=(x^(Subscript[d, B]))mod (Subscript[m, B]).

Bob encrypts the message-signature pair (x, σ) to Alice using Alice’s public encryption key (Subscript[e, A]). The result is the encrypted message-signature pair (y, β) = ((x^(Subscript[e, A]))mod (Subscript[m, A]), (σ^(Subscript[e, A]))mod (Subscript[m, A])).

Bob send the encrypted message signature pair (y,β) to Alice.

Alice

Alice receives the encrypted message signature pair (y,β) to Bob. At this stage, she doesn’t know if the sender of the message is really Bob.

She decrypts the message using her private decryption exponent (Subscript[d, A]).

She computes (x, σ)=((y^(Subscript[d, A]))mod (Subscript[m, A]), (β^( (Subscript[d, A])))mod (Subscript[m, A])).

Alice looks up Bob’s public key (Subscript[e, B]) and public modulus (Subscript[m, B]). She checks Bob’s digital signature by computing z=(σ^(Subscript[e, B]))mod (Subscript[m, B]). If z=x, then the message is authentic. If z≠x, then the sender of the message is not Bob.