Assignment Series A3 # Public Key Algorithms

1. Introduction

This challenge will ill help you guide your self-study regarding public key algorithms and hard problems. You will also practice a bit with popular algorithms. It is crucial to understand public-key algorithms as they are the foundation of basically all hybrid communication schemes, digital signatures and various applications. E.g. PGP, S/MIME, TLS, IPSEC, x.509 Certificates, Mobile App Signing to name a few popular. Very large parts of our digital lifes depend on it.

1. Symmetric ciphers rely on shared secrets and thus lack the convenience of key distribution that comes with public key algorithms. Can you think of problems that still remain unsolved? Maybe read through Wikipedia, Public-key Crypto, Alteration of Public Keys first.
2. The class of public key algorithms make use of so-called "hard problems" to assure that private keys cannot be calculated from public keys. The problems are basically a kind of one-way functions. Easy to calculate in one direction but hard to reverse. Describe the two popular "hard problems" in simple words and give an example of an algorithm or protocol that makes use of it.
3. RSA is by far the most popular public key algorithm. That said, you are expected to describe the key setup (components and criteria) as well as the encryption and decryption formulas. Make a simple example with very small numbers. Follow the guide at Wikipedia, RSA (cryptosystem).
4. Do the same for ElGamal. Follow the guide at Wikipedia, ElGamal(encryption).
5. Alice sent Bob an encrypted number: 587. Mallory has intercepted the message and also holds a copy of Bob’s RSA public key (n,e 2773,17). Proof that small hard problems are not hard and calculate the plaintext number.
6. The Diffie-Hellman key agreement protocol is an early follower of the public key algorithm idea.
   • How does the protocol work? Use Alice and Bob as parties.
   • What is the public and what is the private key composed of?
   • Assuming Mallory is in the position to rely and alter communication. Could you describe an attack that may allow interception of traffic?

2. Answers

1. Challanges and Problems of Public Key Cryptography

   There are some concerns that come with the continued use of public key encryption, including the administration of certificates. The digital keys used to encrypt and sign messages are packaged into digital certificates, which are issued by certificate authorities (CAs) — trusted hubs for verifying identities. This ecosystem is known as public key infrastructure (PKI).

   Unfortunately, PKI has historically had its issues. For instance, Dutch CA DigitNotar went out of business after someone hacked its infrastructure and issued fraudulent certificates in 2011.

   Another danger to public key cryptography is mathematic in nature. Trapdoor functions rely, in part, on the difficulty of factoring large prime numbers, which are used to create the keys. If someone found a way to easily find large prime numbers and then used that solution to solve the prime factorization problem, it would be catastrophic for public key cryptography.

   Public-key cryptography also has vulnerabilities to attacks such as the man in the middle attack. In this situation, a malicious third party intercepts a public key on its way to one of the parties involved. The third party can then instead pass along his or her own public key with a message claiming to be from the original sender

2. Hard problems in cryptography

   Hardness assumptions on mathematical problems lie at the heart of modern cryptography. They are often what ensure one cannot break an encryption scheme. More formally, a hardness assumption on a particular problem is the assumption that there is no efficient algorithm that can solve it.

   Factoring :
   Factoring numbers is a hard problem. While it may seem very simple for low numbers, it is considered a hard problem for large numbers. Example is the RSA algorithm

   DDH:
   The decisional Diffie-Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most notably the ElGamal and Cramer-Shoup cryptosystems.

3. RSA Key algorithm:
   The security of RSA is based on the fact that it is easy to calculate the product n of two large primes p and q. However, it is very difficult to determine only from the product n the two primes that yield the product. This decomposition is also called the factorization of n.

   As a starting point for RSA choose two primes p and q.
   p = 11
q = 13

   n = p * q = 143 (First part of pulic key)

   φ(n) = (p − 1) * (q − 1) = 120

   120 = 2 2 2 3 5 (splitting in to prime numbers)

   Next step is to determine the value e. This value must be another prime number than above.

   e = 7 (Second part of public key)

   Public key = (143,7)

   For the private key we need a value d

   value d must be between 0 and φ(n)

Next step is to create a value table:

e	φ(n)	x	R	a	b
7	120	0	7	-17	1
120	7	17	1	1	-17
7	1	7	0	0	1	here at botom line a is always 0 and b is 1

b = a – (xb) = 0 – (17 1) = -17

b = a – (x b) = 1 – (0 (-17)) = 1

d = -17 –> value d must be between 0 and φ(n)!

d = φ(n) + (d) = 120 – 17 = 103

Private key is 103

4. ElGamal algorithm:

   On Alice machine we need a prime p, a primitive root of p called g and a private key x

   p = 11
g = 2
x = 5

Alice public key: p:11 g:2 h:10

Bobs private key for encryption r should be greater than or equal to 0 and less than p -1
Bobs message m should be greater than 0 and less than or equal to p

r = 2
m = 3

Bobs encrypted message: c1:4, c2:3

5. Given is the second part of public key (n,e 2773,17).
   Prime numbers of 2773 are 47 and 59
   https://www.calculatorsoup.com/calculators/math/prime-factors.php
   φ(n) = 46 * 58 = 2668

   value d must be between 0 and 2668

e	φ(n)	x	R	a	b
17	2668	0	17	-156	1
2668	17	156	1	1	-156
17	1	17	0	0	1	here at botom line a is always 0 and b is 1

b = a – (xb) = 0 – (156 1) = -156
b = a – (x b) = 1 – (0 (-156)) = 1

d = -156
d = 2668 – 156 = 2510

private key = 2510

Maybe there was something wrong in my calculation here. I’ve discovered a really cool tool that helps with encryption and decryption:
http://umaranis.com/rsa_calculator_demo.html

Message 587 decrypt to ASCII Code = 1072

Decrypted message = a

6. Diffie-Hellmann

The Diffie-Hellman protocol is a scheme for exchanging information over a public channel. If two people (usually referred to in the cryptographic literature as Alice and Bob) wish to communicate securely, they need a way to exchange some information that will be known only to them. In practice, Alice and Bob are communicating remotely (e.g. over the internet) and have no prearranged way to exchange information.

The main idea is that each of them has some secret information that is known only to them, which they combine into a suitable key, or password, which they can then use to set up a secure communication platform. The Diffie-Hellman protocol allows them to accomplish this even if an antagonist is monitoring their messages, as long as their secret information remains secret.

Principle of Diffie-Hellman-Merkle key exchange
a: private key of Alice
b: private key of Bob
p: publicly known prime number
g: publicly known natural number less than p
A: public key of Alice
B: public key from Bob
K: secret session key for Alice and Bob

Because the math behind it is not so easy to understand, there is a cool example with paint:

Diffie Hellmann Mitm

"The Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. In this attack, an opponent Carol intercepts Alice’s public value and sends her own public value to Bob. When Bob transmits his public value, Carol substitutes it with her own and sends it to Alice. Carol and Alice thus agree on one shared key and Carol and Bob agree on another shared key. After this exchange, Carol simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants. Possible solutions include the use of digital signatures and other protocol variants."

PDF Report:
publik_key#1