[Note] Diffie-Hellman Key Exchange

[ Diffie-Hellman 키 교환 알고리즘]

[공격자가 키를 알아내려고 할 경우 - 소스]

#include <stdio.h>

int main()
{
 unsigned int idx = 0;
 unsigned int exp = 0;

 unsigned int tmp[3] = {7, 11, 0};
 unsigned int result = 0;

 for(idx = 0; idx < 500; idx++)
 {
  tmp[2] = 1;

  for(exp = 1; exp <= idx; exp++)
  {
   tmp[2] *= tmp[0];
  }

  result = tmp[2] % tmp[1];

  if(result == 4)
  {
   printf("result 4 is appears (7 ^ %d = %d mod %d), (%d / %d = %d + %d) \n"
    , idx
    , result
    , tmp[1]
    , tmp[2]
    , tmp[1]
    , tmp[2] / tmp[1]
    , tmp[2] % tmp[1]
    );
  }
 }

 return 0;
}

[결과]

result 4 is appears (7 ^ 6 = 4 mod 11), (117649 / 11 = 10695 + 4)
result 4 is appears (7 ^ 12 = 4 mod 11), (956385313 / 11 = 86944119 + 4)
result 4 is appears (7 ^ 36 = 4 mod 11), (1729633 / 11 = 157239 + 4)
result 4 is appears (7 ^ 42 = 4 mod 11), (1626129905 / 11 = 147829991 + 4)
result 4 is appears (7 ^ 52 = 4 mod 11), (1798631905 / 11 = 163511991 + 4)
result 4 is appears (7 ^ 57 = 4 mod 11), (1626598087 / 11 = 147872553 + 4)
result 4 is appears (7 ^ 69 = 4 mod 11), (1396718503 / 11 = 126974409 + 4)
result 4 is appears (7 ^ 71 = 4 mod 11), (-280270089 / 11 = 364972473 + 4)
result 4 is appears (7 ^ 72 = 4 mod 11), (-1961890623 / 11 = 212097879 + 4)
result 4 is appears (7 ^ 74 = 4 mod 11), (-1643360015 / 11 = 241055207 + 4)
result 4 is appears (7 ^ 87 = 4 mod 11), (-1307672201 / 11 = 271572281 + 4)
result 4 is appears (7 ^ 96 = 4 mod 11), (964604161 / 11 = 87691287 + 4)
result 4 is appears (7 ^ 103 = 4 mod 11), (148461559 / 11 = 13496505 + 4)
result 4 is appears (7 ^ 114 = 4 mod 11), (-853907791 / 11 = 312823591 + 4)
result 4 is appears (7 ^ 122 = 4 mod 11), (-440630927 / 11 = 350394215 + 4)
result 4 is appears (7 ^ 123 = 4 mod 11), (1210550807 / 11 = 110050073 + 4)
result 4 is appears (7 ^ 132 = 4 mod 11), (1077900641 / 11 = 97990967 + 4)
result 4 is appears (7 ^ 141 = 4 mod 11), (640937191 / 11 = 58267017 + 4)
result 4 is appears (7 ^ 148 = 4 mod 11), (741311201 / 11 = 67391927 + 4)
result 4 is appears (7 ^ 157 = 4 mod 11), (509225831 / 11 = 46293257 + 4)
result 4 is appears (7 ^ 176 = 4 mod 11), (502539393 / 11 = 45685399 + 4)
result 4 is appears (7 ^ 189 = 4 mod 11), (-1112414105 / 11 = 289323017 + 4)
result 4 is appears (7 ^ 192 = 4 mod 11), (694051329 / 11 = 63095575 + 4)
result 4 is appears (7 ^ 196 = 4 mod 11), (-30069919 / 11 = 387717943 + 4)
result 4 is appears (7 ^ 197 = 4 mod 11), (-210489433 / 11 = 371316169 + 4)
result 4 is appears (7 ^ 198 = 4 mod 11), (-1473426031 / 11 = 256503751 + 4)
result 4 is appears (7 ^ 208 = 4 mod 11), (2104418177 / 11 = 191310743 + 4)
result 4 is appears (7 ^ 218 = 4 mod 11), (433693297 / 11 = 39426663 + 4)
result 4 is appears (7 ^ 220 = 4 mod 11), (-223864927 / 11 = 370100215 + 4)
result 4 is appears (7 ^ 221 = 4 mod 11), (-1567054489 / 11 = 247992073 + 4)
result 4 is appears (7 ^ 228 = 4 mod 11), (2133165665 / 11 = 193924151 + 4)
result 4 is appears (7 ^ 233 = 4 mod 11), (2023311943 / 11 = 183937449 + 4)
result 4 is appears (7 ^ 242 = 4 mod 11), (1098879665 / 11 = 99898151 + 4)
result 4 is appears (7 ^ 251 = 4 mod 11), (-1073037801 / 11 = 292902681 + 4)
result 4 is appears (7 ^ 257 = 4 mod 11), (149481479 / 11 = 13589225 + 4)
result 4 is appears (7 ^ 265 = 4 mod 11), (1626253127 / 11 = 147841193 + 4)
result 4 is appears (7 ^ 273 = 4 mod 11), (1103844999 / 11 = 100349545 + 4)
result 4 is appears (7 ^ 287 = 4 mod 11), (1151926967 / 11 = 104720633 + 4)
result 4 is appears (7 ^ 300 = 4 mod 11), (-35996895 / 11 = 387179127 + 4)
result 4 is appears (7 ^ 301 = 4 mod 11), (-251978265 / 11 = 367544457 + 4)
result 4 is appears (7 ^ 302 = 4 mod 11), (-1763847855 / 11 = 230101767 + 4)
result 4 is appears (7 ^ 310 = 4 mod 11), (115713041 / 11 = 10519367 + 4)
result 4 is appears (7 ^ 324 = 4 mod 11), (768382817 / 11 = 69852983 + 4)
result 4 is appears (7 ^ 333 = 4 mod 11), (45505255 / 11 = 4136841 + 4)
result 4 is appears (7 ^ 339 = 4 mod 11), (2118494679 / 11 = 192590425 + 4)
result 4 is appears (7 ^ 354 = 4 mod 11), (-898221775 / 11 = 308795047 + 4)
result 4 is appears (7 ^ 371 = 4 mod 11), (556873431 / 11 = 50624857 + 4)
result 4 is appears (7 ^ 379 = 4 mod 11), (-203558377 / 11 = 371946265 + 4)
result 4 is appears (7 ^ 380 = 4 mod 11), (-1424908639 / 11 = 260914423 + 4)
result 4 is appears (7 ^ 390 = 4 mod 11), (-1273180271 / 11 = 274707911 + 4)
result 4 is appears (7 ^ 399 = 4 mod 11), (405913655 / 11 = 36901241 + 4)
result 4 is appears (7 ^ 401 = 4 mod 11), (-1585067385 / 11 = 246354537 + 4)
result 4 is appears (7 ^ 408 = 4 mod 11), (-1739171775 / 11 = 232345047 + 4)
result 4 is appears (7 ^ 419 = 4 mod 11), (-1387222441 / 11 = 264340441 + 4)
result 4 is appears (7 ^ 422 = 4 mod 11), (924072593 / 11 = 84006599 + 4)
result 4 is appears (7 ^ 440 = 4 mod 11), (1769886529 / 11 = 160898775 + 4)
result 4 is appears (7 ^ 451 = 4 mod 11), (567916375 / 11 = 51628761 + 4)
result 4 is appears (7 ^ 454 = 4 mod 11), (1521788305 / 11 = 138344391 + 4)
result 4 is appears (7 ^ 488 = 4 mod 11), (1906387905 / 11 = 173307991 + 4)
result 4 is appears (7 ^ 494 = 4 mod 11), (1438438225 / 11 = 130767111 + 4)

즉, secret 값을 충분히 크게 잡는다면 알아내기 힘들다. 단지 계산하기 위한 시간이 걸리겠지만... 맞아????