RSA Encoding/Decoding

Recall the setup:

Alice selects two distinct primes (Subscript[p, A]) and (Subscript[q, A]) and computes (Subscript[m, A])=(Subscript[p, A])*(Subscript[q, A]) and (Subscript[n, A])=((Subscript[p, A])-1)((Subscript[q, A])-1).

She chooses a number (Subscript[e, A]), relatively prime to (Subscript[n, A])=((Subscript[p, A])-1)((Subscript[q, A])-1).

She finds the multiplicative inverse of (Subscript[e, A]) modulo (Subscript[n, A]), that is, she finds an integer (Subscript[d, A]) such that (Subscript[e, A])(Subscript[d, A])≡1(mod (Subscript[n, A])).

Alice makes (Subscript[m, A]) and (Subscript[e, A]) public. (Subscript[m, A]) is called the RSA modulus, and (Subscript[e, A]) the public key or the encryption key.

Alice keeps the other information a secret ((Subscript[p, A]), (Subscript[q, A]), (Subscript[n, A]), (Subscript[d, A])). The integer (Subscript[d, A]) is called the private key or the decryption key.

Encryption function:  E(x)=(x^(Subscript[e, A]))(mod (Subscript[m, A])), where 1⩽x⩽(Subscript[m, A])-1.

Decryption function: D(y)=(y^(Subscript[d, A]))(mod (Subscript[m, A])), where 1⩽y⩽(Subscript[m, A])-1.

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]

Digital signatures with RSA

We want a digital signature that can help confirm the identity of the sender of a message. The sender should not be able to deny that it/he/she is the author the message (non - repudiation).
Authentication is the process of insuring that both ends of the connection are in fact who they say they are. This applies not only to the entity trying to access a service (such as an end user) but to the entity providing the service, as well (such as a file server or Web site).

Two party-communication via RSA

Alice and Bob

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 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]).

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 sends 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.

Bob

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.

Example

Alice and Bob want to communicate via RSA and digitally sign their messages so that they cannot be forged by an evil third party.

RSA Setup

Bob:  selects the primes (Subscript[p, B])=5,  (Subscript[q, B])=13, and computes  (Subscript[m, B])=(Subscript[p, B])*(Subscript[q, B])= 65,  (Subscript[n, B])=((Subscript[p, B])-1)((Subscript[q, B])-1)=48. He chooses (Subscript[e, B])=5, relatively prime to 48, and computes (Subscript[d, B])=29 (the multiplicative inverse of 5 modulo 48). He makes (Subscript[m, B])= 65 (RSA modulus) and (Subscript[e, B])=5 (RSA encryption key) public. He keeps the other information private.

Alice: (Subscript[p, A])=3,  (Subscript[q, A])=11,  (Subscript[m, A])=(Subscript[p, A])*(Subscript[q, A])= 33,  (Subscript[n, A])=((Subscript[p, A])-1)((Subscript[q, A])-1)=20,  (Subscript[e, A])=3,  (Subscript[d, A])=7.

She makes (Subscript[m, A])=33 and (Subscript[e, A])=3 public and keeps the rest a secret.

Message-Signature Pair

Bob wants to send Alice the message x = 9.

First he digitally signs the message using his private RSA key.

σ=(x^(Subscript[d, B]))mod (Subscript[m, B])= (9^29)mod 65 = (3^58)mod 65 = (3^10)mod 65 = 29 mod 65.
The digital signature of the message is σ = 29.

9^29
3^10
PowerMod[9, 29, 65]

The message signature pair is (x,σ) = (9, 29).

Encrypted Message-Signature Pair

Bob encrypts the message signature pair (x,σ) using Alice’s public modulus (Subscript[m, A]) and encryption key (Subscript[e, A]).

y = (x^(Subscript[e, A]))mod (Subscript[m, A]) =  (9^3)mod 33 = 3

β = (σ^(Subscript[e, A]))mod (Subscript[m, A]) =  (29^3)mod 33 = 2

PowerMod[{9,29}, 3, 33]

The encrypted message signature pair is (y, β) = (3, 2).

Bob sends this encrypted and digitally signed message to Alice.

Decoding the message

Alice receives the pair (y, β) = (3, 2) (from Bob?). She decrypts the message using her private decryption key (Subscript[d, A])=7.

x = (y^(Subscript[d, A]))mod (Subscript[m, A]) = (3^7)mod 33 = 9

σ = (β^( (Subscript[d, A])))mod (Subscript[m, A]) = (2^7)mod 33 = 29

PowerMod[{3,2}, 7, 33]

The decrypted message-signature pair is (x,σ) = (9,29).

Is the signature valid? Is the message authentic?

Alice checks to see if the signature σ is valid. She looks up Bob’s public RSA modulus (Subscript[m, B])= 65 and encryption key (Subscript[e, B])=5.

She computes z = (σ^(Subscript[e, B]))mod (Subscript[m, B]) = (29^5)mod 65 = 9

She compares z with x, z = x = 9, so the digital signature is valid and the message is authentic.

Exercise:

Alice receives several encrypted message-signature pairs. What are the decoded messages? Which messages are authentic (that is, sent from Bob)?

L={{3,8},{3, 28}, {6,27},{6,28},{6,10}, {6,6}}

A more realistic example:

A user logs on to his bank' s homepage www.bank.com to do online banking. When the user opens www.bank.com homepage, they receive a public key along with all the data that his web browser displays. The public key could be used to encrypt data from the client to the server but the method would not be safe or fast. In fact, any evil third party could easily impersonate the bank, issue a fake public key (for which it would have a matching private key) and the naive client could get tricked into encrypting sensitive information with the fake public key and send it over to the evil third party. 
The safe procedure is to use asymmetric key cryptography in a handshake protocol that authenticates the bank to the client and also helps exchange a key for a symmetric cryptosystem that will be used in further communications. Let’s revisit the handshake protocol:

When you go to security on a page using https (just click on the information button i, left to the lock sign), you can see a message like
“The connection to this site is encrypted and authenticated using a strong protocol (TLS 1.2), a strong key exchange asymmetric cipher (RSA), and a strong symmetric cipher (AES_256)”. 
The RSA-2048 is used to encrypt the AES-256 key. AES (Advanced Encryption System) is a symmetric cipher, depending on a 256-bit (random) key. To do a brute-force attack a 256 bit cipher key you have to try most of the (2^256)possibilities.

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.  SSL is what keeps your passwords, communications and credit card details safe on the way between your computer and the servers you want to send this data to.

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 networks such as wifi 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.

The main purposes of the SSL are the following:

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

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

SSL Handshake protocol has two parts:

server authentication (based on RSA).

(optional) client authentication (RSA).

How it works:

(Client Hello) 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.).

(Server Hello) 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. By sending its digital certificate, it proves its identity to the client.

The client verifies the authenticity of the server’s digital certificate. The client checks if the certificate is verified and trusted by one of several Certificate Authorities (CAs) that it implicitly trusts. Your browser has a pre-installed list of trusted SSL certificates from Certificate Authorities (CAs) that you can view, add and remove from. In Mozilla Firefox for example, you can check this list of trusted CAs from Preferences->Advanced->Certificates->View Certificates->Authorities. These certificates are controlled by a centralized small group of extremely secure, reliable and trustworthy organizations like Symantec (VeriSign), Comodo, GoDaddy, GlobalSign, DigiCert, Entrust, Verizon, Deutsche Telekom and so on. If a server presents a certificate from that list then you know you can trust them. The role of the Certificate Authority is to issue digital certificates that contain a public key and the identity of the owner of the public key and to certify that a certain public key does indeed belong to whoever is identified in the certificate. The digital certificate is digitally signed with the private key of a Certificate Authority. If the user trusts the CA and can verify the CA’s digital signature, then the user will trust the digital certificates signed by the CA. If the server cannot be authenticated, the user is warned of the problem and informed that the digital certificate is not trusted and an encrypted and authenticated connection cannot be established.

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.

If the server has requested client authentication (an optional step in the handshake), the client also digitally signs another piece of data that is unique to this handshake and known by both the client and server. In this case, the client sends both the signed data and the client's own certificate (assuming that the server has previously issued a unique certificate to each of its clients) to the server along with the encrypted master key.

The server decrypts (recovers) the master key k, using his RSA private decryption key. This step is crucial to proving the authenticity of the server.

If the server has requested client authentication, the server attempts to authenticate the client. If the client cannot be authenticated, the session ends.

The server authenticates itself to the client by returning a message like “Finished” signed with his private RSA key and encrypted with the symmetric cipher with key k. The message that ends the Handshake usually also contains a hash of all data previously exchanged between the parties.

The client also sends the message “Finished” encrypted with key k.

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

Exercise

John decides to use RSA encryption. He chooses p=23, q=31 and e=19. He makes public m=713 and e=19. He also publicizes the way in which English text is to be numerically encoded. Two letter-blocks are interpreted as base 26 representations. For example, the numeric equivalent of H is 7, of I is 8, so the numeric equivalent of the 2-letter block HI will be 78 in base 26, that is, HI=7*26+8=190. So if John decodes an RSA message and discovers that the number is 190, he know that this means HI. Say HI to John, using RSA.