RSA

[mak1610]

Нужно написать простенькую программу на c ++ (хватит исходного кода), которая: на входе строка. На выходе должны получить зашифрованную строку алгоритмом RSA. Помогите или подскажите идею.

[milsy]

на википедии же есть все даже
http://ru.wikipedia.org/wiki/RSA

[Alexu007]

Пытаюсь разобраться с википедией, споткнулся вот на чём:

$(5 \cdot d) \mod 396 = 1$

как вычислить d?

[Pavia]

У Кнута всё доходчиво расписано.

$5*d=n*396+1$
$d=(n*396+1) div 5$ при таких n, при которых на цело делится.
Т.е $(n*396+1) mod 5=0$ отсюда найдём n

$(n*396 mod 5 +1) mod 5=0$
$(n*(396 mod 5) +1) mod 5=0$
$(n*(1 mod 5) +1) mod 5=0$
$(n+1) mod 5=0$
$n=5*K+4$ где k от 0 до бесконечности
$d=396*K+317$ где k от 0 до бесконечности

[Alexu007]

Спасибо. Правда не очень понятно, из каких вычислений в последней строке возникло "магическое" число 317.

Есть и ещё вопросы по собственно алгоритму RSA. Шифруем файлы, файлы состоят из байт. Если шифровать по 1 байту - то каждый зашифрованный байт будет однозначно сответствовать исходному. И где тут криптостойкость? Текст будет доступен лингвистическому анализу, т.к. одной букве будет всегда соответствовать одно, путь и большое, число.

И ещё по примеру из википедии: $X^3\mod 9173503 = 4051753$, это действительно криптостойкая формула? Потому что доступен открытый ключ 3, 9173503 и собственно зашифрованное число 4051753. То есть все коэффициэнты формулы известны. X не вычислить никак, хотя бы простым перебором?

[Pavia]

Цитата:

Спасибо. Правда не очень понятно, из каких вычислений в последней строке возникло "магическое" число 317.

$n=5*K+4$ подставляется во 2 строчку $d=(n*396+1) div 5$ и упрощается

Советую читать:
Дональд Эрвин Кнут (Donald E. Knuth)-Искусство программирования. том 2 читать с 4 главы
А также статьи создателя PGP.

Цитата:

И ещё по примеру из википедии: $X^3\mod 9173503 = 4051753$, это действительно криптостойкая формула? Потому что доступен открытый ключ 3, 9173503 и собственно зашифрованное число 4051753. То есть все коэффициенты формулы известны. X не вычислить никак, хотя бы простым перебором?

Вычислить можно. Но формула считается стойкой.
Перебор не эффективен. Тут числа маленькие. А возьмите 256 или 1024 битные числа. Вам не хватит не атомов во всей вселенной чтобы построить такой процессор. Ни времени существования вселенной. Даже если перебирать не все числа, а просты, то время поиска не сильно изменится.

[Alexu007]

Pavia в сообщении #524510 писал(а):

Цитата:

Спасибо. Правда не очень понятно, из каких вычислений в последней строке возникло "магическое" число 317.

$n=5*K+4$ подставляется во 2 строчку $d=(n*396+1) div 5$ и упрощается

Советую читать:
Дональд Эрвин Кнут (Donald E. Knuth)-Искусство программирования. том 2 читать с 4 главы
А также статьи создателя PGP.

Уж извините за тупость и настырность, но теперь у вас непонятно откуда взялась цифра 4. Можно предположить, что 4 это 5 - 1, но попытка пересчитать d например для показателя степени 13 (вместо пятёрки) даёт неверные результаты и для $n=13*K+12$, и для $n=13*K+4$

Я подсчитал перебрав варианты в цикле:

Используется синтаксис C++

void __fastcall TForm1::Button1Click(TObject *Sender)
{
for(int i = 14; i < 2000; i++)
   if((13 * i) % 396 == 1) {Label1->Caption = i; break;}

return;
}

получилось 61 (а вместо 4 должна быть 2), но хотелось бы добить математику...

[Alexu007]

Не хотите помогать? Ну и не надо! Я сам всё нашёл: http://kastaneda.kiev.ua/crypto/rsa/keygen.html

[Sonic86]

Pavia в сообщении #524510 писал(а):

Цитата:

И ещё по примеру из википедии: $X^3\mod 9173503 = 4051753$, это действительно криптостойкая формула? Потому что доступен открытый ключ 3, 9173503 и собственно зашифрованное число 4051753. То есть все коэффициенты формулы известны. X не вычислить никак, хотя бы простым перебором?

Вычислить можно. Но формула считается стойкой.
Перебор не эффективен. Тут числа маленькие. А возьмите 256 или 1024 битные числа. Вам не хватит не атомов во всей вселенной чтобы построить такой процессор. Ни времени существования вселенной. Даже если перебирать не все числа, а просты, то время поиска не сильно изменится.

Следует также сказать, что формула крипостойкая потому, что для обращения функции нужно разлагать $9173503$ на множители. Когда модуль большой - это сложно сделать. В этом принцип RSA.
Хотя в Кнуте нужно глянуть: для хорошей работы RSA обычно выбирают некрайние значения. При малых $d=3$ у нас сразу получается, что модуль $m=pq$ и $p,q \equiv 2 \pmod 3$ - сокращаем число простых уже в 2 раза, это уже может быть существенно для взлома. Вот при $d$ порядка $10^3$ такой прием уже не эффективен.

-- Пт янв 13, 2012 04:12:19 --

Alexu007 в сообщении #524451 писал(а):

Есть и ещё вопросы по собственно алгоритму RSA. Шифруем файлы, файлы состоят из байт. Если шифровать по 1 байту - то каждый зашифрованный байт будет однозначно сответствовать исходному. И где тут криптостойкость? Текст будет доступен лингвистическому анализу, т.к. одной букве будет всегда соответствовать одно, путь и большое, число.

А Вы шифруйте не по одному байту, а целиком.

[Alexu007]

Sonic86 в сообщении #526298 писал(а):

А Вы шифруйте не по одному байту, а целиком.

Целиком можно зашифровать не более произведения простых чисел - не так много даже в случае больших чисел, никакой файл крупнее нескольких десятков байт целиком не зашифруешь.

Поэтому обычная практика - собственно сообщение шифруют симметричным шифром, а с помощью RSA шифруют ключ к симметричному шифру. Не сам придумал - прочитал в приведённой мной ссылке...

[Евгений Машеров]

Если блоки шифра по 1 байту, то режим простой замены (кодовой книги) действительно нестоек. Поэтому используют режим сцепления (когда очередной блок перед шифрованием складывают с зашифрованным предыдущим) или иные, при которых очередиииной блок зависит не только от оригинала, но и от других блоков (обратной связи по шифртексту, обратной связи по выходу и др.)

[mak1610]

Скажите пожалуйста, почему в функции Эйлера используются именно простые числа?

[Sonic86]

mak1610 в сообщении #526751 писал(а):

Скажите пожалуйста, почему в функции Эйлера используются именно простые числа?

Функция Эйлера $\varphi (n)$ - это порядок группы $\mathbb{Z}_n^{\times}$. А какие элементы $a$ в нее входят? Только те, которые взаимно просты с $n$, т.е. если $n=p_1^{a_1}...p_s^{a_s}$, то $p_1 \not | a, ..., p_s \not | a$. - Вот видите, как естественно появляются здесь простые числа.

[Alexu007]

О, сделал черновой вариант, случайные пятизначные простые числа в диапазоне 10000 - 65535. Только закрытый ключ долго вычисляет, зараза, до нескольких минут... Таки никакой формулы для вычисления этого ключа не существует, только перебор вариантов?

[Sonic86]

Закрытый ключ $e$ для открытого ключа $d$ соотносятся как $ed \equiv 1 \pmod{(p-1)(q-1)}$, а значит он находится быстро алгоритмом Евклида.