поясните работу RSA

Тема в разделе "WASM.CRYPTO", создана пользователем featurelles, 5 сен 2009.

  1. featurelles

    featurelles New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2009
    Сообщения:
    562
    Хочу написать алгоритм 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 (желательно программно, через какой-либо алгоритм) и что делать дальше)
     
  2. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    Бррр...
    Небось по русскоязычной литературе 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
     
  3. featurelles

    featurelles New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2009
    Сообщения:
    562
    Ага, а по другому не получится, английского не знаю ( хоть и надо бы выучить )

    Cсылка ничего мне не дала, (из-за проблем с английским).
    Если знаете, где можно посмотреть реализацию RSA на си., то пожалуйста дайте ссылку. ( по коду, будет проще разобраться. )
     
  4. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    >> Cсылка ничего мне не дала
    Там жеж псевдокод есть...

    с ссылкой на код тебе будет также сложно разобраться.
    Потому как весь RSA суть одна математика.
    Разбираться тебе надо с математическими алгоритмами.
    В общем тебе надо Дональд Кнут, том 2. а еще лучше Брюс Шнаер, прикладная криптография, глава 11
    Они выходили на русском.
    Если с поиском совсем плохо - могу выложить.
     
  5. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    вот тебе Шнайер на русском: http://creatorcray.googlepages.com/schneier.rar
    думаю пригодится в любом случае
    тебя интересуют главы 11 полностью и 19.3 конкретно по RSA
    Английский - учи, он реально очень нужен если хочешь заниматься криптографией да и вообще программированием.
     
  6. featurelles

    featurelles New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2009
    Сообщения:
    562
    CreatorCray
    ОГРОМНОЕ СПАСИБО за ответ. Буду учиться английскому, и разбираться в криптографии.
    Если не сложно, накидайте пожалуйста список литературы. От простого к сложному, с чем следовало бы ознакомиться (не с нуля но всёже чтоб пробелов в знаниях не было) в перспективе серьёзно заниматься криптографией.
     
  7. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    основны в общем то достаточно хорошо расписаны в двух книгах:

    1) HANDBOOK of APPLIED CRYPTOGRAPHY - Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone
    2) Applied Cryptography: Second Edition - Bruce Schneier

    ну и соответственно другие книги этих авторов
     
  8. Ra_

    Ra_ New Member

    Публикаций:
    0
    Регистрация:
    4 мар 2007
    Сообщения:
    289
    НЕ, не только, пусть и русскоязычную тоже читает, а там выберет...

    Можно зайти на
    http://www.infanata.org/
    и задать в поиске криптография и криптология (нужна регистрация на сайте)

    можно поискать и в теме
    http://cracklab.ru/f/index.php?action=vthread&forum=2&topic=2387
    :)
     
  9. OLS

    OLS New Member

    Публикаций:
    0
    Регистрация:
    8 янв 2005
    Сообщения:
    322
    Адрес:
    Russia
    Какое то из идательств обещало еще в 2006 выпустить Менезеса на русском.
    Никто не в курсе - не появлялось ли ?
    На мой субъективный взгляд именно эта книга - лучший учебник по криптографии, из когда либо изданных.
     
  10. CreatorCray

    CreatorCray Member

    Публикаций:
    0
    Регистрация:
    5 авг 2006
    Сообщения:
    201
    >> На мой субъективный взгляд именно эта книга - лучший учебник по криптографии, из когда либо изданных.
    Согласен. Из всей "базовой" литературы что я видел - этот лучший.
     
  11. Stariy

    Stariy Member

    Публикаций:
    0
    Регистрация:
    22 окт 2003
    Сообщения:
    529
    Адрес:
    Russia
    Реализация на си есть в openssl 0.9.8, кажется, номер версии не помню точно.
    Найти несложно через гугл.
    Правда, там наворочено куча лишнего, так что разобраться непросто вот так с ходу, но вполне реально, если аккуратно вникать, не спеша.
     
  12. featurelles

    featurelles New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2009
    Сообщения:
    562
    Спасибо =)
     
  13. Guest

    Guest Guest

    Публикаций:
    0
    http://www.polarssl.org/?page=show_source&type=source&file=rsa
     
  14. featurelles

    featurelles New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2009
    Сообщения:
    562
    im1111
    Спасибо!!!
     
  15. Guest

    Guest Guest

    Публикаций:
    0
    featurelles
    Эти исходники отличаются хорошей наглядностью, а для практического использования и получения выигрыша в скорости лучше использовать Crypto++.
     
  16. Johnikum

    Johnikum Member

    Публикаций:
    0
    Регистрация:
    6 июн 2003
    Сообщения:
    97
    в приложении к книге "Вельшенбах М. - Криптография на C и C++ в действии" есть пример реализации RSA
     
  17. rommanio

    rommanio New Member

    Публикаций:
    0
    Регистрация:
    4 май 2008
    Сообщения:
    151
    Еще могу посоветовать "Книгу шифров" Саймона Сингха.
     
  18. featurelles

    featurelles New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2009
    Сообщения:
    562
    Спасибо =)
    Почитаю.