Хочу написать алгоритм RSA на си , но для того чтоб его написать, мне нужно сначала разобраться, как он вообще работает. ( если кто видел реализацию на си в нете, плиз дайте ссылочку ) Хотелось бы чтоб мне пояснили некоторые моменты. 1) Сначала выбираем два простых числа N = P*Q 2) Подсчитываем количество чисел от 1 до N-1 которые взаимно просты с N (функция Эйлера) 3) Если N произведение двух простых чисел P и Q то f(N)=(P-1)*(Q-1) 4) Ключ шифрования E выбирается, как случайное число, которое взаимно просто с f(N) 5) Ключ дешифровки D отыскивается, как решение следующего уравнения E*D = S*f(N)+1 при каком-либо целом S Решить его можно с помощью расширения алгоритма Евклида.(позволяет найти два числа J и K) такие, что J*A +K*B=R где А - делимое, B - делитель, R - остаток например A=7253 B=120 R=53 Снизу, вывод моей реализации алгоритма Евклида: 53 = 7253 - 60 * 120 14 = 120 - 2 * 53 11 = 53 - 3 * 14 3 = 14 - 1 * 11 2 = 11 - 3 * 3 1 = 3 - 1 * 2 1 = 3 - 1 * 2 2 = 11 - 3 * 3 3 = 14 - 1 * 11 11 = 53 - 3 * 14 14 = 120 - 2 * 53 53 = 7253 - 60 * 120 Вопрос в следующем, как найти J и K (желательно программно, через какой-либо алгоритм) и что делать дальше)
Бррр... Небось по русскоязычной литературе RSA учился? Совет на будущее: бери англоязычную - там не выпендриваются и нормальным языком пишут. >> Подсчитываем количество чисел от 1 до N-1 которые взаимно просты с N (функция Эйлера) это нафиг не нужно. >> Если N произведение двух простых чисел P и Q у тебя ж в пункте 1 декларируется что N = P*Q, где P и Q - два простых числа >> f(N)=(P-1)*(Q-1) С целью ускорения последующих вычислений берут f(N)=LCM(P-1,Q-1), LCM == lesser common multiple. Простейший алгоритм евклида: http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Formal_description_of_the_algorithm
Ага, а по другому не получится, английского не знаю ( хоть и надо бы выучить ) Cсылка ничего мне не дала, (из-за проблем с английским). Если знаете, где можно посмотреть реализацию RSA на си., то пожалуйста дайте ссылку. ( по коду, будет проще разобраться. )
>> Cсылка ничего мне не дала Там жеж псевдокод есть... с ссылкой на код тебе будет также сложно разобраться. Потому как весь RSA суть одна математика. Разбираться тебе надо с математическими алгоритмами. В общем тебе надо Дональд Кнут, том 2. а еще лучше Брюс Шнаер, прикладная криптография, глава 11 Они выходили на русском. Если с поиском совсем плохо - могу выложить.
вот тебе Шнайер на русском: http://creatorcray.googlepages.com/schneier.rar думаю пригодится в любом случае тебя интересуют главы 11 полностью и 19.3 конкретно по RSA Английский - учи, он реально очень нужен если хочешь заниматься криптографией да и вообще программированием.
CreatorCray ОГРОМНОЕ СПАСИБО за ответ. Буду учиться английскому, и разбираться в криптографии. Если не сложно, накидайте пожалуйста список литературы. От простого к сложному, с чем следовало бы ознакомиться (не с нуля но всёже чтоб пробелов в знаниях не было) в перспективе серьёзно заниматься криптографией.
основны в общем то достаточно хорошо расписаны в двух книгах: 1) HANDBOOK of APPLIED CRYPTOGRAPHY - Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone 2) Applied Cryptography: Second Edition - Bruce Schneier ну и соответственно другие книги этих авторов
НЕ, не только, пусть и русскоязычную тоже читает, а там выберет... Можно зайти на http://www.infanata.org/ и задать в поиске криптография и криптология (нужна регистрация на сайте) можно поискать и в теме http://cracklab.ru/f/index.php?action=vthread&forum=2&topic=2387
Какое то из идательств обещало еще в 2006 выпустить Менезеса на русском. Никто не в курсе - не появлялось ли ? На мой субъективный взгляд именно эта книга - лучший учебник по криптографии, из когда либо изданных.
>> На мой субъективный взгляд именно эта книга - лучший учебник по криптографии, из когда либо изданных. Согласен. Из всей "базовой" литературы что я видел - этот лучший.
Реализация на си есть в openssl 0.9.8, кажется, номер версии не помню точно. Найти несложно через гугл. Правда, там наворочено куча лишнего, так что разобраться непросто вот так с ходу, но вполне реально, если аккуратно вникать, не спеша.
featurelles Эти исходники отличаются хорошей наглядностью, а для практического использования и получения выигрыша в скорости лучше использовать Crypto++.
