Pohlig-HellmanPohlig-Hellman is a good example of a shared secret key encryption which uses discrete logarithms [Blog] |
Examples
The following are some examples:
- message = 101, p = 293. Try
- message = 777, p = 2621. Try
- message = 1024, p = 9887. Try
- message = 1024, p = 99971. Try
- message = 9999, p = 104729. Try
- message = 1234, p = 104551. Try
Outline
First we determine create a prime number, such as:
p = 5
we then use (p-1) where:
e.d mod (p-1) = 1
For example:
e.d mod 4 =1
and solution is (e.d) = 21, so we can us e=3, d=7:
3 x 7 mod 4 = 1
The cipher is:
Cipher = Message^e mod p
and:
Plain = Cipher^d mod 5
For example if we have a Message of 2 we get:
Cipher = 2^3 mod 5 = 3
and:
Message = 3^7 mod 5 = 2
This matches the original message.
Code
Outline code:
public string poh1(UInt64 message, UInt64 p) { string working = ""; bool artn=get_if_prime(Convert.ToInt32(p), ref working); if (artn==false) return ("P value is not a prime: " + p); if (message >= p) return ("Message value is greater than p. Make message smaller that p."); UInt64 factor = 1, factor2 = 0; for (UInt64 i=2;i<1000000;i++) { if (get_if_prime(Convert.ToInt32(i), ref working)) continue; if ((i % (p-1 )) ==1) { UInt64 num = i; for (UInt64 j = 2; j < num / 2; j++) { if((num%j) == 0) { factor = j; factor2 = i / j; if (i!=j) break; // stop loop when factor is found } } if (factor != factor2) break; } } string rtn = "Encryption keys (e,d): "+Convert.ToString(factor) + "," + Convert.ToString(factor2); string c = encr(message,factor, p); rtn +="\nCipher is: "+c; string d = encr(Convert.ToUInt64(c), factor2, p); rtn +="\nDecipher is: "+d; return (rtn); } public static string encr(UInt64 m, UInt64 e, UInt64 p) { Microsoft.SolverFoundation.Common.BigInteger message = (Microsoft.SolverFoundation.Common.BigInteger)m; Microsoft.SolverFoundation.Common.BigInteger eval= (Microsoft.SolverFoundation.Common.BigInteger)e; Microsoft.SolverFoundation.Common.BigInteger pval = (Microsoft.SolverFoundation.Common.BigInteger)p; Microsoft.SolverFoundation.Common.BigInteger val = Microsoft.SolverFoundation.Common.BigInteger.Power(m, eval) % p; return Convert.ToString(val); }