DH.java 4.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182
  1. // CRYPTO LIBRARY FOR EXCHANGING KEYS
  2. // USING THE DIFFIE-HELLMAN KEY EXCHANGE PROTOCOL
  3. // The diffie-hellman can be used to securely exchange keys
  4. // between parties, where a third party eavesdropper given
  5. // the values being transmitted cannot determine the key.
  6. // Implemented by Lee Griffiths, Jan 2004.
  7. // This software is freeware, you may use it to your discretion,
  8. // however by doing so you take full responsibility for any damage
  9. // it may cause.
  10. // Hope you find it useful, even if you just use some of the functions
  11. // out of it like the prime number generator and the XtoYmodN function.
  12. // It would be great if you could send me emails to: lee.griffiths@first4internet.co.uk
  13. // with any suggestions, comments, or questions!
  14. // Enjoy.
  15. // Adopted to ms-logon for ultravnc and ported to Java by marscha, 2006.
  16. //import java.lang.Math;
  17. public class DH {
  18. public DH() {
  19. maxNum = (((long) 1) << DH_MAX_BITS) - 1;
  20. }
  21. public DH(long generator, long modulus) throws Exception {
  22. maxNum = (((long) 1) << DH_MAX_BITS) - 1;
  23. if (generator >= maxNum || modulus >= maxNum)
  24. throw new Exception("Modulus or generator too large.");
  25. gen = generator;
  26. mod = modulus;
  27. }
  28. private long rng(long limit) {
  29. return (long) (java.lang.Math.random() * limit);
  30. }
  31. //Performs the miller-rabin primality test on a guessed prime n.
  32. //trials is the number of attempts to verify this, because the function
  33. //is not 100% accurate it may be a composite. However setting the trial
  34. //value to around 5 should guarantee success even with very large primes
  35. private boolean millerRabin (long n, int trials) {
  36. long a = 0;
  37. for (int i = 0; i < trials; i++) {
  38. a = rng(n - 3) + 2;// gets random value in [2..n-1]
  39. if (XpowYmodN(a, n - 1, n) != 1) return false; //n composite, return false
  40. }
  41. return true; // n probably prime
  42. }
  43. //Generates a large prime number by
  44. //choosing a randomly large integer, and ensuring the value is odd
  45. //then uses the miller-rabin primality test on it to see if it is prime
  46. //if not the value gets increased until it is prime
  47. private long generatePrime() {
  48. long prime = 0;
  49. do {
  50. long start = rng(maxNum);
  51. prime = tryToGeneratePrime(start);
  52. } while (prime == 0);
  53. return prime;
  54. }
  55. private long tryToGeneratePrime(long prime) {
  56. //ensure it is an odd number
  57. if ((prime & 1) == 0)
  58. prime += 1;
  59. long cnt = 0;
  60. while (!millerRabin(prime, 25) && (cnt++ < DH_RANGE) && prime < maxNum) {
  61. prime += 2;
  62. if ((prime % 3) == 0) prime += 2;
  63. }
  64. return (cnt >= DH_RANGE || prime >= maxNum) ? 0 : prime;
  65. }
  66. //Raises X to the power Y in modulus N
  67. //the values of X, Y, and N can be massive, and this can be
  68. //achieved by first calculating X to the power of 2 then
  69. //using power chaining over modulus N
  70. private long XpowYmodN(long x, long y, long N) {
  71. long result = 1;
  72. final long oneShift63 = ((long) 1) << 63;
  73. for (int i = 0; i < 64; y <<= 1, i++){
  74. result = result * result % N;
  75. if ((y & oneShift63) != 0)
  76. result = result * x % N;
  77. }
  78. return result;
  79. }
  80. public void createKeys() {
  81. gen = generatePrime();
  82. mod = generatePrime();
  83. if (gen > mod) {
  84. long swap = gen;
  85. gen = mod;
  86. mod = swap;
  87. }
  88. }
  89. public long createInterKey() {
  90. priv = rng(maxNum);
  91. return pub = XpowYmodN(gen,priv,mod);
  92. }
  93. public long createEncryptionKey(long interKey) throws Exception {
  94. if (interKey >= maxNum){
  95. throw new Exception("interKey too large");
  96. }
  97. return key = XpowYmodN(interKey,priv,mod);
  98. }
  99. public long getValue(int flags) {
  100. switch (flags) {
  101. case DH_MOD:
  102. return mod;
  103. case DH_GEN:
  104. return gen;
  105. case DH_PRIV:
  106. return priv;
  107. case DH_PUB:
  108. return pub;
  109. case DH_KEY:
  110. return key;
  111. default:
  112. return (long) 0;
  113. }
  114. }
  115. public int bits(long number){
  116. for (int i = 0; i < 64; i++){
  117. number /= 2;
  118. if (number < 2) return i;
  119. }
  120. return 0;
  121. }
  122. public static byte[] longToBytes(long number) {
  123. byte[] bytes = new byte[8];
  124. for (int i = 0; i < 8; i++) {
  125. bytes[i] = (byte) (0xff & (number >> (8 * (7 - i))));
  126. }
  127. return bytes;
  128. }
  129. public static long bytesToLong(byte[] bytes) {
  130. long result = 0;
  131. for (int i = 0; i < 8; i++) {
  132. result <<= 8;
  133. result += (byte) bytes[i];
  134. }
  135. return result;
  136. }
  137. private long gen;
  138. private long mod;
  139. private long priv;
  140. private long pub;
  141. private long key;
  142. private long maxNum;
  143. private static final int DH_MAX_BITS = 31;
  144. private static final int DH_RANGE = 100;
  145. private static final int DH_MOD = 1;
  146. private static final int DH_GEN = 2;
  147. private static final int DH_PRIV = 3;
  148. private static final int DH_PUB = 4;
  149. private static final int DH_KEY = 5;
  150. }