Генерю модуль и закрытый ключ. А открытый не могу получить по закрытому. Прога уходит в бесконечный цикл... Может я в формулах что-то напутал? Уточните пожалуста. 1. Берем простые p и q 2. Считаем модуль: n = p*q 3. Считаем закрытый ключ d. Это произвольное число, взаимно простое с (p-1)*(q-1) 4. Считаем открытый ключ e. Это число, для которого справедливо: (e*d) mod ((p-1)*(q-1)) = 1 Так вот я, имея p, q и d просто гоню циклом e от двойки и вперед. И прога виснет. Все ли правильно в формулах и где может быть косяк?
По математике не скажу, но e это экспонента, её вроде бы выбирают, а n = p*q это есть открытый ключ, вместе с экспонентой, я бы проверил на RSA Tool, а ещё лучше в CrypTool. Там есть демонстрация RSA криптосистемы с формулами, картинками и на примере реальных чисел, например: Choose two prime numbers p and q. The number N = pq is the public RSA modulus and phi(N) = (p-1)(q-1) is the Euler number. Public key e is coprime to phi(N). The private key d = e^(-1) (mod phi(N)) is calculated from this. Код (Text): Prime number p = 211 Prime number q = 227 RSA modulus N = 47897 (public) phi(N) = (p-1)(q-1) = 47460 (secret) Public key e = 2^16+1 private key d = 45953 Ещё в MSDN можно посмотреть http://msdn.microsoft.com/library/default.asp?url=/library/en-us/seccr ypto/security/private_key_blobs.asp http://msdn.microsoft.com/library/default.asp?url=/library/en-us/seccr ypto/security/public_key_blobs.asp
bogrus Крипт тул качнул, посмотрю... Получается открытый ключ считается через закрытый... Я думал наоборот.
Так не делают. Для больших p,q этот цикл будет практически неосуществим. Закрытый ключ d вычисляют, обращая открытый ключ e по модулю (p-1)*(q-1), используя расширенный алгоритм Евклида. И правильно думал. Обычной закрытый ключ вычисляют по открытому. Более того, открытый ключ e часто полагают равным маленькому простому числу с небольшим количеством единиц в двоичной записи, например, 2^4+1=17 или 2^16+1=65537.
RElf Так, стоп, что-то я сам уже запутался... Я думал что: 1. Сначала вычесляется закрытый ключ. 2. Потом зная закрытый ключ, вычисляется открытый. Получается что: 1. Берем открытый ключ, для простоты 2^k+1. 2. И уже по нему вычисляем закрытый по Евклиду. Все правильно?
Выдираю из доки, по-моему тут хорошо понятен порядок действий: Алгоритм RSA работает следующим образом: берутся два достаточно больших простых числа p и q и вычисляется их произведение n = p*q; n называется модулем. Затем выбирается число e, удовлетворяющее условию 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1). Затем вычисляется число d таким образом, что (e*d - 1) делится на (p - 1)*(q - 1). Код (Text): e - открытый (public) показатель d - частный (private) показатель (n:e) - открытый (public) ключ (n:d) - частный (private) ключ Делители (факторы) p и q можно либо уничтожить либо сохранить вместе с частным (private) ключом. Ещё у Z0MBiE ищи, статья + исходники (часть в аттаче) 258036027__zombie_rsa.zip
_DEN_ Напрасно! :о) _Математически_ нет никакой разницы между _закрытым_ и _открытым_ ключами. Это определяется лишь тем, какое из чисел распространяется открыто, а какое остается у пользователя. Ведь сами числа e и d _взаимно_обратны по выбранному модулю, следовательно абсолютно равноправны в отношении "закрытости/открытости" ;о) Единственно, как уже сказал RElf, как правило " ", но и это не является обязательным требованием.
