#encryption #rsa #pseudocode
#шифрование #rsa #псевдокод
Вопрос:
Я делаю проект, в котором мне нужно либо найти, либо создать RSA и алгоритм Elgamal, алгоритм тройного DES и алгоритм цифровой подписи хэширования.
Я пытаюсь собрать свой код воедино, но я продолжаю зацикливаться на кодировании RSA и Elgamal. Мне было интересно, есть ли у кого-нибудь полезные ссылки на псевдокод RSA: в частности, вычисление больших простых чисел (также известных как p и q) [Кажется, я не могу понять права Эйлера] и нахождение взаимного простоты для phi(n) = (p-1) (q-1) (иначе e). Цель всех уравнений, которые я пытаюсь закодировать, — эффективно находить большие простые числа. Если кто-нибудь знает более простой способ сделать это [эффективное вычисление больших простых чисел], это было бы весьма признателен.
Кроме того, я немного зацикливаюсь на дополнении… Я могу справиться со своим проектом, просто выполняя шифрование / дешифрование без добавления, но я хочу идти дальше и дальше… любые ссылки на полезные схемы заполнения / псевдокод схемы заполнения были бы очень полезны.
Я попытался найти в Google хороший псевдокод, но я действительно нашел только какой-то неоднозначный псевдокод для вычисления большого простого числа… (либо это, либо я просто очень плотный).
Любая помощь была бы весьма признательна (и просто для уточнения, мне не нужно, чтобы кто-то писал для меня весь алгоритм, мне просто нужен толчок в правильном направлении).
Спасибо, что уделили мне время.
Комментарии:
1. Что сбивает с толку в этом псевдокоде:
do {p = random_prime_of_the_right_size(); }until (isPrime(p));?2. Да, я понимаю, о чем ты говоришь… Я думаю, что я не очень хорошо объяснил себя в своем посте. Поэтому поиск простых чисел для меня не проблема, это эффективный поиск больших простых чисел. Итак, в основном мне нужно найти способ находить большие простые числа за O (n) время [хотя время O (1) было бы впечатляющим, ха-ха], и прямо сейчас все реализации, о которых я могу думать, выполняются за O (n ^ 2) время. Я отредактирую свой пост, чтобы указать, что я ищу эффективную реализацию.
Ответ №1:
I'm trying to put my code together, but I keep getting hung up on coding RSA and Elgamal. I was wondering if anyone had any useful links to RSA pseudocode: specifically, calculating large primes (aka p and q) [I can't seem to get euler's right], and finding a coprime to phi(n) = (p-1)(q-1) (aka e)
Генерировать большие простые числа непросто, поскольку не известен надлежащий способ вычисления простого числа (к счастью, если бы он был, RSA был бы нарушен). Обычно вы берете случайные числа и выполняете тест на простоту, такой как Miller-Rabine, который очень хорошо подготавливается (50 выполнений сужают его до 1/2 ^ 50-процентной вероятности того, что проверяемое число является простым). Единственное требование заключается в том, что случайные числа должны быть действительно случайными, иначе найденный ключ небезопасен. Linux /dev /random — хороший источник для запуска генератора случайных чисел. Или предпочтительный модуль шифрования языка (C: openssl, Java: SecureRandom …).
Вокруг RSA нет реального псевдокода, поскольку это математический процесс. Самым близким к псевдокоду, который я мог получить, была реализация python для простого поколения. Есть аккуратный пример python для грамотных программ. Также здесь
Что касается заполнения, википедия довольно хорошо объясняет одну схему заполнения. Также эта запись в блоге очень помогла мне понять заполнение. Ссылки о заполнении: http://rdist.root.org/2009/10/06/why-rsa-encryption-padding-is-critical / http://www.symantec.com/connect/blogs/common-rsa-implementation-mistake-explained
Я надеюсь, что это подтолкнет вас в правильном направлении.