Реалізуйте Діффі-Хеллмана

Для одного з найважливіших алгоритмів у криптографії ця вправа не може бути набагато простішою.

Встановіть змінну “p” на 37 та “g” на 5. Цей алгоритм настільки простий, що я навіть не збираюся його пояснювати. Просто зробіть те, що роблю я.

Згенеруйте “a”, випадкове число по модулю 37. Тепер згенеруйте “A”, яке є “g”, зведеним до степеня “a” по модулю 37 — A = (g**a) % p.

Зробіть те саме для “b” та “B”.

“A” та “B” – це відкриті ключі. Згенеруйте з ними сеансовий ключ; встановіть “s” на “B”, зведений до степеня “a” по модулю 37 — s = (B**a) % p.

Зробіть те саме з A**b, перевірте, чи ви отримали однакові “s”.

Щоб перетворити “s” на ключ, можна просто хешувати його, щоб створити 128 біт ключового матеріалу (або SHA256, щоб створити ключ для шифрування та ключ для MAC-адреси).

Гаразд, це було весело, тепер повторіть вправу з великими числами, як у реальному світі. Ось параметри, які подобаються NIST:

p:
ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024
e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd
3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec
6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f
24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361
c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552
bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff
fffffffffffff
 
g: 2

Це дуже легко зробити на Python, Ruby або інших мовах високого рівня, які автоматично перетворюють фіксовані числа на великі, але це не є “складним” ніде.

Зауважте, що вам потрібно буде написати власний modexp (це математика для дошки, не панікуйте), оскільки ви перевантажите свою бібліотеку bignum, підводячи “a” до 1024-бітного степеня. Ви можете знайти modexp процедури на Rosetta Code для більшості мов.