Diffe-Hellman algorithm

[xieyuschen]

Diffe-Hellman is used to exchange a private key during an unsafe communication channel. It is Not an encrypting algorithm.

• a and b is the private key of the client and server
• p is a large primer number known by both sides. It's generated by the client side and sends it to the server side after verifying the signature from the server side. In practice, it is generated a pseudo prime number.

  Run openssl genrsa:

  Generating RSA private key, 2048 bit long modulus (2 primes)
  ................+++++
  ...............+++++
  e is 65537 (0x010001)

  Each . means a potential prime candidate was generated, and each + means a round of Miller-Rabin was passed. According to this answer, even three rounds of Miller-Rabin will be enough to make it very unlikely that a randomly generated non-prime passes the Miller-Rabin test. So as you can see, OpenSSL stops after five passed rounds and moves on to generate a new number.

• g is small for easy computing.
• Client: A = g^a mod p.
• Server: B = g^b mod p.
• exchange the output A and B.

The server and client exchanges: A, B, g and p: So both side could calculate the session key:

client_key = B^a mod p = ((g^a)^b) mod p = g^ab mod p.
server_key = A^b mod p = ((g^b)^a) mod p = g^ab mod p.

But the listener could only get A, B, g and p. To get an a from an equalisation A = g^a mod p is a dlb(Discrete Logarithm Problem) question. It's imposible to get the anwser now.

[xieyuschen]

In RSA:

• N=pq
• ed = 1 mod φ(N)
• φ(N) = (q-1)*(p-1)

The public key is (N,e), and the private key is d. In a real case, message M could be encrypted:

• C=M^d mod N We can also use a public key to decrypt it:
• C^e mod N = (M^d)^e mod N = M^ed mod N Here we need the Euler Theorem:
• If x is relatively prime to n then x^φ(N) = 1 mod N So
• M<N.
• M^ed mod N= M*M^ed-1 mod N = M mod N = M.

The RSA PUBLIC/PRIVATE KEY is not the key pair files we use in normal life, that file is a kind of RSA key expression, see RFC3447

[xieyuschen]

In ECC, y^2 = x^3 + ax +b. P = mQ, both P and Q belong to F*p. The key pair generator choose a random m and Q in curve, and then calculate P.

• public key: P.
• private key: m.

The public key encrypts and the private key decrypts:

• a, b, P, Q are public.
• M, could be converted to a point Qm on the curve.
• Generate a random integer r.
• C = Qm + rP.
• Send C and rQ.

So we could decrypt by private key:

• C = Qm + rP = Qm + r(mQ) = Qm + m(rQ)
• Qm = m(rQ) - C.
• Serialize Qm to binary format.

[xieyuschen]

it's an INVILIAD operation to encrypt a message with a private key. Signature instead.