Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.12.2006, 01:51
Новичок

Отправить личное сообщение для Дмитрий Посмотреть профиль Найти все сообщения от Дмитрий
 
Регистрация: 16.12.2006
Сообщений: 6

проблема реализации шифрования файлов Rsa
занялся реализацией RSA, алгоритм знаю и понимаю. довел до рабочего состояния и решил реализовать шифрование файлов. Считываю файлы по-байтово, что бы в сумме биты составляли длину ключа (кратного 8-ми). Вот только столкнулся с проблемой, возникает ситуация, когда длина шифруемого блока равна длине ключа, но по размеру превышает его, шифрование получается не корректным. Подскажите как бы лучше реализовать шифрование файлов. Суть не важно, но работаю В Delphi.
  #2  
Старый 20.12.2006, 04:56
Новичок

Отправить личное сообщение для 1nsane Посмотреть профиль Найти все сообщения от 1nsane
 
Регистрация: 20.12.2006
Сообщений: 1

Пишу задачу для курсовой по алг шифрования с открытым ключом. Реализую алгоритм RSA на Delphi. Но столкнулся с проблемами. Не могли бы вы Дмитрий помочь мне:

1. Удалось ли вам реализовать работу с большими числами, если да то как? Какие типы данных используете?

2. Как вы находите d? Оно должно быть взаимнопростым с phi(n) или с n?(Просто в разных источниках разная информация и я уже совсем запутался)

Условия для d: взаимнопростое с phi(n),т.е. НОД(d,phi(n))=1, d<phi(n), d>1?

3. Как вы находите e?

Условия для e: e*d mod phi(n)=1, e<phi(n), e>1?

Вы сначала генерируете случайное число, а потом проверяете его на соответствие условиям?

4. Как шифруете/дешифруете?
Преобразовываете символы в числа с помощью ord(), шифруете, и обратно chr()?

Что-то вроде:

type
massive=array [1..u] of char;

var enc,dec:massive;
p,q,n,phi,d,e:integer;

function Encrypt(s:string;e:integer;n:integer):massive;
var i,j,ch,ech:integer;
begin
for i:=1 to length(s) do
begin
ch:=ord(s[i]);
ech:=1;
for j:=1 to e do ech:=(ech*ch) mod n;
enc[i]:=chr(ech);
end;
result:=enc;
end;

function Decrypt(enc:massive;d:integer;n:integer):massive;
var i,j,ch,dch:integer;
begin
for i:=1 to length(ish_text) do
begin
ch:=ord(enc[i]);
dch:=1;
for j:=1 to d do dch:=(dch*ch) mod n;
dec[i]:=chr(dch);
end;
result:=dec;
end;

Дело в том что при дешифровании не все сиволы расшифровываются верно.

Не могли бы вы привести процедуры по этим вопросам

P.S.: До шифрования файлов у меня дело пока не дошло.

Спасибо.
  #3  
Старый 27.12.2006, 19:37
незарегистрированный

 
Сообщений: n/a

>Подскажите как бы лучше реализовать шифрование файлов. Суть не важно, но работаю В Delphi.

считывать порциями на 1 байт меньшей чем ключ.
Тогда данные будут всегда меньше, чем ключ,
а при расшифровке можно проверить этот нулевой байт,
если вдруг больше нуля - значит неправильный ключ или шифротекст.
Своебразный parity-byte-check.
  #4  
Старый 27.12.2006, 20:22
незарегистрированный

 
Сообщений: n/a

http://www.mytempdir.com/1136708

забираем генераторы ключей RSA, генераторы простых чисел и шифровальшики файлов RSA. Языки - Mirackl С++, Delphi, JAVA.
Быстродействие у всех примерно одинаковое, т.к. ядро написано на ASM.
  #5  
Старый 30.12.2006, 01:16
Новичок

Отправить личное сообщение для Дмитрий Посмотреть профиль Найти все сообщения от Дмитрий
 
Регистрация: 16.12.2006
Сообщений: 6

To 1nsane
По порядку:
1) Работу с большими числами реализовал через модульную арифметику, свойство таково: (a*b) mod n =( (a mod n)*b) mod n. писал функцию. Конечно могу написать код, но я думаю интерес как раз таки в реализации, так что если уж совсем невмоготу спрашивайте - напишу.

2) Лучше напишу весь алгоритм:
Алгоритм основан на использовании операции возведения в степень модульной арифметики. Его можно представить в виде следующей последовательности шагов.
Шаг 1. Выбираются два больших простых числа р и q. Про*стыми называются числа, которые делятся только на самих себя и на 1. Величина этих чисел должна быть больше 200.
Шаг 2. Получается открытая компонента ключа п:

n=p*q.

Шаг 3. Вычисляется функция Эйлера по формуле:

f(p,q) = (p-1)(q-1).

Функция Эйлера показывает количество целых положитель*ных чисел от 1 до п, которые взаимно просты с п. Взаимно про*стыми являются такие числа, которые не имеют ни одного общего делителя, кроме 1.
Шаг 4. Выбирается большое простое число d, которое является взаимно простым со значением f(p,q).
Шаг 5. Определяется число е, удовлетворяющее условию:

e*d =1(mod f(p,q)).

Данное условие означает, что остаток от деления про*изведения e*d на функцию f(p,q) равен 1. Число е принимается в качестве второй компоненты открытого ключа. В качестве сек*ретного ключа используются числа d и n.
Шаг 6. Исходная информация, независимо от ее физической природы, представляется в числовом двоичном виде. Последова*тельность бит разделяется на блоки длиной L бит, где L - наи*меньшее целое число, удовлетворяющее условию: L>=log2(n+1). Каждый блок рассматривается как целое положительное число Х(i), принадлежащее интервалу [0,n-1]. Таким образом, исходная информация представляется последовательностью чисел Х(i), i =1,I. Значение I определяется длиной шифруемой последо*вательности.
Шаг 7. Зашифрованная информация получается в виде после*довательности чисел Y(i), вычисляемых по формуле:

Y(i) = (X(i))^e(mod n).

Шаг 8. Для расшифрования информации используется сле*дующая зависимость:

X(i) = (Y(i))^d(mod n).

Я думаю здесь все понятно написано.
  #6  
Старый 30.12.2006, 01:18
Новичок

Отправить личное сообщение для Дмитрий Посмотреть профиль Найти все сообщения от Дмитрий
 
Регистрация: 16.12.2006
Сообщений: 6

Сообщение от незарегистрированный Посмотреть сообщение
>Подскажите как бы лучше реализовать шифрование файлов. Суть не важно, но работаю В Delphi.

считывать порциями на 1 байт меньшей чем ключ.
Тогда данные будут всегда меньше, чем ключ,
а при расшифровке можно проверить этот нулевой байт,
если вдруг больше нуля - значит неправильный ключ или шифротекст.
Своебразный parity-byte-check.
Хорошая идея - спасибо.
  #7  
Старый 30.12.2006, 01:32
Новичок

Отправить личное сообщение для Дмитрий Посмотреть профиль Найти все сообщения от Дмитрий
 
Регистрация: 16.12.2006
Сообщений: 6

Сообщение от 1nsane Посмотреть сообщение

Дело в том что при дешифровании не все сиволы расшифровываются верно.
Здесь скорее всего проблема с длиной взятого куска, либо проблема больших чисел. Еще один совет: в процедуре вычисления остатка от деления больших чисел лучше использовать вещественные типы а не целые, а перед result'ом округлять.
  #8  
Старый 31.12.2006, 18:15
незарегистрированный

 
Сообщений: n/a

Цитата:
Работу с большими числами реализовал через модульную арифметику, свойство таково: (a*b) mod n =( (a mod n)*b) mod n.
Согласен, при возведение в степень нужно брать остаток постоянно,
а не в самом конце от результата (да он и ни в какую память не влезет).
Но вылаза за пределы длинного числа до его двойного размера не избежать.
  #9  
Старый 03.01.2007, 03:12
Новичок

Отправить личное сообщение для Дмитрий Посмотреть профиль Найти все сообщения от Дмитрий
 
Регистрация: 16.12.2006
Сообщений: 6

Сообщение от незарегистрированный Посмотреть сообщение
согласен, при возведение в степень нужно брать остаток постоянно,
а не в самом конце от результата (да он и ни в какую память не влезет).
но вылаза за пределы длинного числа до его двойного размера не избежать.
не совсем понял, что вы имели ввиду, но проблему простых чисел можно решить циклом от 1 до величины степени, а в цикле умножать остаток от деления предыдущего шага на основание и снова и находить остаток от деления
  #10  
Старый 03.01.2007, 03:15
Новичок

Отправить личное сообщение для Дмитрий Посмотреть профиль Найти все сообщения от Дмитрий
 
Регистрация: 16.12.2006
Сообщений: 6

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
проблема с использованием русского алфавита в с++ elle Реализация, исходники, языки 9 17.03.2008 21:19