2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: RSA
Сообщение07.01.2012, 20:16 
Аватара пользователя
на википедии же есть все даже
http://ru.wikipedia.org/wiki/RSA

 
 
 
 Re: RSA
Сообщение07.01.2012, 23:38 
Пытаюсь разобраться с википедией, споткнулся вот на чём:

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

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

 
 
 
 Re: RSA
Сообщение08.01.2012, 01:17 
Аватара пользователя
У Кнута всё доходчиво расписано.

$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 до бесконечности

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

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

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

 
 
 
 Re: RSA
Сообщение08.01.2012, 13:01 
Аватара пользователя
Цитата:
Спасибо. Правда не очень понятно, из каких вычислений в последней строке возникло "магическое" число 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 битные числа. Вам не хватит не атомов во всей вселенной чтобы построить такой процессор. Ни времени существования вселенной. Даже если перебирать не все числа, а просты, то время поиска не сильно изменится.

 
 
 
 Re: RSA
Сообщение08.01.2012, 16:55 
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), но хотелось бы добить математику...

 
 
 
 Re: RSA
Сообщение10.01.2012, 15:44 
Не хотите помогать? Ну и не надо! Я сам всё нашёл: http://kastaneda.kiev.ua/crypto/rsa/keygen.html

 
 
 
 Re: RSA
Сообщение13.01.2012, 07:08 
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 байту - то каждый зашифрованный байт будет однозначно сответствовать исходному. И где тут криптостойкость? Текст будет доступен лингвистическому анализу, т.к. одной букве будет всегда соответствовать одно, путь и большое, число.

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

 
 
 
 Re: RSA
Сообщение13.01.2012, 08:29 
Sonic86 в сообщении #526298 писал(а):
А Вы шифруйте не по одному байту, а целиком.

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

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

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

 
 
 
 Re: RSA
Сообщение14.01.2012, 14:55 
Скажите пожалуйста, почему в функции Эйлера используются именно простые числа?

 
 
 
 Re: RSA
Сообщение16.01.2012, 06:33 
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$. - Вот видите, как естественно появляются здесь простые числа.

 
 
 
 Re: RSA
Сообщение16.01.2012, 18:53 
Изображение

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

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

 
 
 [ Сообщений: 19 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group