Encryption-Decryption

Key concept: Plain-Text, Cipher-Text, Key, Algorithm.

Important Terms

• Key
• Random string of bits created specifically for scrambling and unscrambling data.
• Used to encrypt and/or decrypt data.
• Each key is unique and created via algorithm to make sure it is unpredictable.
• Common key lengths are 128 bits for symmetric key algorithms and 2048 bits for public-key algorithms.
• Private key and Public key.
• Cipher
• An algorithm used for encryption or decryption.
• It is a set of steps that are followed as a procedure to encrypt information.
• There are two main types of ciphers, block ciphers and stream ciphers.
• Algorithm
• An algorithm is the procedure that the encryption process follows.
• The specific algorithm is called the cipher,. or code

Identify Pattern

The strong mathematical functions used in Public Key Cryptography have the unique characteristic that they are almost irreversible,

They can only easily be calculated into one direction and not the opposing.

Steps to Encrypt & Decrypt message

Sharing Public key

Encrypt Message using Public key

Sharing Encrypted Message

Decrypt Message

Identify the Issue with Scenario

Recap

• Public key cryptography allows someone to send their public key in an open, insecure channel.
• Having a friend’s public key allows you to encrypt messages to them.
• Your private key is used to decrypt messages encrypted to you.
• Intermediaries—such as the email service providers, Internet service providers, and those on their networks—are able to see metadata this whole time: who is sending what to whom, when, what time it’s received, what the subject line is, that the message is encrypted, and so on.

RSA Crypto System

• The RSA algorithm is named after Ron Rivest, Adi Shamir and Len Adleman, who invented it in 1977.
• The basic technique was first discovered in 1973 by Clifford Cocks [COCK73] of CESG (part of the British GCHQ) but this was a secret until 1997.
• The RSA cryptosystem is the most widely-used public key cryptography algorithm in the world. It can be used to encrypt a message without the need to exchange a secret key separately.
• The RSA algorithm can be used for both public key encryption and digital signatures.
• Its security is based on the difficulty of factoring large integers.

Mathematics behind the algorithm

Key generation

• Choose two distinct primes p and q of approximately equal size so that their product n=pq is of the required bit length.
• Compute ϕ(n)=(p−1)(q−1).
• Choose a public exponent e, 1<e<ϕ(n), which is coprime to ϕ(n), that is, gcd(e,ϕ(n))=1.
• Compute a private exponent d that satisfies the congruence ed≡1(modϕ(n)).
• Make the public key (n,e) available to others. Keep the private values d, p, q, and ϕ(n) secret.

RSA Encryption scheme

• Encryption rule: ciphertext, c= RsaPublic(m)=m^e mod n, where 1<m<n−1.
• Decryption rule: plaintext, m= RsaPrivate(c)=c^d mod n.
• Inverse transformation: m = RsaPrivate(RsaPublic(m)).

RSA Signature scheme

• Signing: signature, s = RsaPrivate(m)=m^d mod n, where 1<m<n−1.
• Verification: check, v = RsaPublic(s)=s^e mod n.
• Inverse transformation: m = RsaPublic(RsaPrivate(m))

Example

• Select primes p=11, q=3.
• n = pq = 11.3 = 33
• phi = (p-1)(q-1) = 10.2 = 20
• Choose e=3
• Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
• and check gcd(e, q-1) = gcd(3, 2) = 1
• therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1

• Compute d such that ed ≡ 1 (mod phi)
• i.e. compute d = (1/e) mod phi = (1/3) mod 20
• i.e. find a value for d such that phi divides (ed-1)
• i.e. find d such that 20 divides 3d-1.
• Simple testing (d = 1, 2, ...) gives d = 7
• Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
• Public key = (n, e) = (33, 3)
• Private key = (n, d) = (33, 7).

​

Encryption & Decryption

• Public key = (n, e) = (33, 3)�Private key = (n, d) = (33, 7).

Encryption:

C = m^e mod n

C = 73 mod 33

C = 343 mod 33

C = 13

Hence the ciphertext c = 13.

Decryption:

M’ = c^d mod n

M’ = 137 mod 33 = 7.

Question

1. In a RSA cryptosystem a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of A is 35. Then calculate the private key of A . If plain text is 2 then generate cipher text and also perform decipher from given cipher text.
2. In a RSA cryptosystem a particular A uses two prime numbers p = 11 and q =13 to generate her public and private keys. If the public key of A is 23. Then calculate the private key of A . If plain text is 2 then generate cipher text and also perform decipher from given cipher text.
3. Perform encryption and decryption using the RSA algorithm for the following:

p = 11; q = 13, e = 11; M = 7 e. p = 17; q = 31, e = 7; M = 2

4. In a public-key system using RSA, you intercept the cipher text C = 10 sent to a user whose public key is e = 5, n = 35. What is the plaintext M?

​

​

Key Generation

Trapdoor Function

Diffie-Hellman Algorithm

Example

Step 1: Alice and Bob get public numbers

P = 23, G = 9

​

Step 2: Alice selected a private key a = 4 and

Bob selected a private key b = 3

​

Step 3: Alice and Bob compute public values

​

Alice: x =(9^4 mod 23) = (6561 mod 23) = 6

Bob: y = (9^3 mod 23) = (729 mod 23) = 16

​

​

Step 4: Alice and Bob exchange public numbers

​

Step 5: Alice receives public key y =16 and

Bob receives public key x = 6

​

​

Step 6: Alice and Bob compute symmetric keys

Alice: ka = y^a mod p = 65536 mod 23 = 9

Bob: kb = x^b mod p = 216 mod 23 = 9

​

Step 7: 9 is the shared secret.

​

RABIN Crypto System

• The algorithm was published in January 1979 by Michael O. Rabin.
• The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of integer factorization.
• It has been mathematically proven to be computationally secure against a chosen-plaintext attack as long as the attacker cannot efficiently factor integers.
• The plaintext is recovered by finding the four square roots of c modulo m, and choosing the correct message from the four possibilities.
• Note that a text message is converted to a number m in the same way as RSA.

​

Key generation�

1. Rabin’s cryptosystem is based on two integers p and q each congruent to 3 modulo 4 which form the private key.
2. The product, n = p × q, is the public key.
3. To encrypt the message m, the ciphertext is c = m² mod n. 

Calculation of Ciphertext c

1. First determine a and b satisfying the equation a × p + b × q = 1 using the extended euclidean algorithm.
2. Compute r = c^(p+1)/4 mod p.
3. Compute s = c^(q+1)/4 mod q.
4. Compute x = (a × p × s + b × q × r) mod n.
5. Compute y = (a × p × s − b × q × r) mod n.
6. Then the four square roots are m₁ = x, m₂ = −x, m₃ = y, and m₄ = −y.
7. The problem with Rabin’s cryptosystem is the decryption into four possible messages.
8. The solution is to pad the message in such a way that only one of the four possible messages fits the padding.
9. This is done by replicating the bits of the last portion of the message, adding them to the end of the message; only the correct decryption will have the trailing bits duplicated.

Example

• Consider p = 7, q = 11, and n = 77.
• By the euclidean algorithm,
• (−3)×7 + 2×11 = 1,
• so a = −3 and b = 2.
• Now we send the message 5 based10 = 101 based 2, padded to the message m = 101101 based 2 = 45 based 10.
• The ciphertext is c = 45^2 mod 77 = 23.
• Decryption first computes r = 23^2 mod 7 = 4 and s = 23^2 mod 11 = 1.
• Then x = (−3)×7×1 + 2×11×4 mod 77 = 67 and y = (−3)×7×1 − 2×11×4 mod 77 = 45.
• Thus two of the square roots are 67 and 45, and the other two are 77 − 67 = 10 and 77 − 45 = 32.
• Now 10 based 10 = 001010 based 2, 32 based 10 = 100000 based 2, 45 based 10 = 101101 based 2 and 67 based 10 = 1000011 based 2, so only 101101 based 2 has the required redundancy and the payload is 101 based 2 = 5 based 10.

​

https://www.youtube.com/watch?v=D7PCISyZ5Ls

ELGAMAL Cryptosystem

• Presented in 1984 by Tather Elgamal Key aspects.

Key aspect

• Based on the Discrete Logarithm problem.
• Randomized encryption Application

Application:

• Establishing a secure channel for key sharing
• Encrypting messages

Algorithm

Mathematics Process

• Find the Multiplicative Inverse

https://www.youtube.com/watch?v=shaQZg8bqUM

• Find Primitive Root of Primary Number

https://www.youtube.com/watch?v=NsaXVGmuX18

​

Chapter 7 Asymmetric-Key Cryptography

• 7.1 Introduction
• 7.2 RSA Cryptosystem
• 7.3 RABIN Cryptosystem
• 7.4 ELGAMAL Cryptosystem

Topics Beyond Syllabus Topics

• Forward Secrecy
• Search Encrypt
• Live Key

References

• https://medium.com/coinmonks/a-laymans-explanation-of-public-key-cryptography-and-digital-signatures-1090d4bd072e
• https://medium.com/searchencrypt/what-is-encryption-how-does-it-work-e8f20e340537
• https://medium.com/coinmonks/a-laymans-explanation-of-public-key-cryptography-and-digital-signatures-1090d4bd072e
• https://medium.com/@cvsudheer/asymmetric-encryption-in-brief-ec27bf33568f
• https://ssd.eff.org/en/module/deep-dive-end-end-encryption-how-do-public-key-encryption-systems-work
• https://medium.com/blockwhat/public-key-cryptography-a-comprehensive-guide-1e8489e08104.
• https://www.commonlounge.com/discussion/2be4d294aa9e44d4b67f6644cd9b5ced
• https://www.di-mgt.com.au/public-key-crypto-discrete-logs-3-elgamal.html
• https://wwwmayr.in.tum.de/konferenzen/Jass05/courses/1/presentations/Meier%20Andreas%20The%20ElGamal%20Cryptosystem.pdf

Thank you

​

​

Question, if any ?