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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 03.01.2007, 10:55
незарегистрированный

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

Сообщение от дмитрий Посмотреть сообщение
не совсем понял, что вы имели ввиду, но проблему больших чисел можно решить циклом от 1 до величины степени, а в цикле умножать остаток от деления предыдущего шага на основание и снова и находить остаток от деления
советую реализовать быстрый алгоритм степени через возведения в квадрат. а про цикл забудьте - уже для скромных больших чисел длиной, скажем, 64бит это будут петафлопсы...
  #12  
Старый 13.03.2007, 23:24
незарегистрированный

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

а как вы генерируете простые больше числа ?
  #13  
Старый 29.03.2007, 23:54
незарегистрированный

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

Кто-нибудь может пояснить доказательство мат части, лежащей в основе алгоритма.
А именно доказательство, того что дешифровка приведет к исходному результату.
Если s это число которое мы кодируем, а D и Е соответсвенно опрераторы кодирования и декодирования, то
E( D ( s ) ) = s = s ^ ( e * d ) mod m = s ^ ( 1 + h*phi( m ) ) mod m = [ этот переход непонятен ] = s mod m.
Где m - основание алгоритма. m = p * q - произведение двух простых чисел.
phi ( m ) - функция Эйлера
h - произвольное целое
e и d - те самые взаимно обратные числа в кольце phi( m );
( e * d ) mod phi( m ) = 1

Заранее благодарю !
  #14  
Старый 31.03.2007, 15:31
Аватар для CD_Eater
Пользователь

Отправить личное сообщение для CD_Eater Посмотреть профиль Найти все сообщения от CD_Eater
 
Регистрация: 21.09.2006
Адрес: Москва
Сообщений: 91

Вы бы почитали основы теории чисел. В любой книжке по криптографии обычно перед изложением RSA идёт краткий рассказ про используемые формулы из теории чисел.

Переход, который вам непонятен - это просто применение малой теоремы Ферма.
http://kvant.mccme.ru/1972/10/malaya_teorema_ferma.htm
  #15  
Старый 18.04.2007, 00:30
ScoobyDoo

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

не подкскажете побробнее как шивровать двоичные файлы? простой текст, к примеру, понятно, из любого сообщения можно создать числовой аналог, переведя например в 256-ичную систему по аски-кодам символов, и это число уже шифровать...а вот как шифровать любой большой файл не пойму
  #16  
Старый 20.04.2007, 02:25
незарегистрированный

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

люди добрые, ну помогите же мне =)
главная цель - наиболее быстро шифровать и расшифровывать файлы.
сейчас я делаю, но расшифровка идёт очень медленно.
шифрую: считываю блоки, равные 1/3 длины n, чтобы числовое представлениt блока исходного файла не превосходило n.
числовое представление получаю так:
intr = 1 //на случай, если первый(е) символ имеет аски-код 0
for i in range(len(res)): //цикл от 0 до длины блока
intr*=256
intr+=ord(res[i]) //добывляю аски код символа
потом шифрую, но в файл-криптограмму пишу сначала длину получившегося зашифрованного блока, потом разделитель( например точка), потом сам блок.
при расшифровке сначала до разделителя считываю из файла длину блока, а затем сам расшифрованный блок и его уже расшивровываю и пишу в новый открытый файл. но так ОЧЕНЬ долго расшифровывается.
Посоветуйте пожалуйста как ускорить процесс.
И может быть я не разумно болучаю из блока его числовой представление с помощью этих аски кодов? как ещё можно? а то длина блока получается маленькой.
Жду ваших советов =)
  #17  
Старый 25.04.2007, 21:26
незарегистрированный

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

Советую поработать над побайтовом считывании файла, n выбирать кратным 8, шифровать в фиксированную длину (дописвать нулевые биты спереди) и так же записывать в файл.
  #18  
Старый 19.05.2007, 16:18
незарегистрированный

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

Здравствуйте, помогите пожалуйста. В качестве курсовой работы мне нужно реализавать Rsa-шифрование. Подскажите, как генерировать большие простые числа. Заранее благодарю.
  #19  
Старый 20.05.2007, 02:40
незарегистрированный

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

реализую РСА кодирование но наткнулся вот на какую фигню...
дописал всё доконца вроде как работает , но расшифрование происходит неверное ...
начал выяснять в чём дело взял большие числа из примера в книги...
неудаётся найти ключ d в этом алгоритм... он ищется но со значениями в книге расходится...
вот алгоритм нахождения д :

e:=strtoint(edit3.text); // мы сами вводим простое число... нод его и Ф равен 1(всё правильно вообщем )
for d:=2 to f-1 do
begin
if ((d*e) mod f) = 1 then break; // если такое д находится то прыгаем из цикла
end;

label6.caption:=inttostr(d);

и так значения : p=2357 q=2551 получили n=6012707 f=(p-1)(q-1)=6007800
выбрали e = 3674911 , и вот d ищется по ф-ле ed=1(mod f) в книги получилось
d=422191 у меня d=3527239
возможно из-за этого и происходит неправиьное декодирование ... помогите не могу понять ошибку...
  #20  
Старый 20.05.2007, 02:44
незарегистрированный

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

вот само кодирование , но раскодировать нормально не получается
выдаёт совсем другие символы
procedure TForm1.Button5Click(Sender: TObject);
var i,t,j,x,m:integer;w:char ;

begin
s:=edit4.text;
i:=0;
while i<=length(s) do
begin
setlength(cry,i+1);
SetLength(mas,i+1);
mas[i]:=s[i];
inc(i);
end;
i:=1;
while i<=length(s) do
begin
w:=mas[i];
x:=ord(w);
label10.Caption:=label10.Caption+' '+inttostr(x);
m:=x;
for t:=1 to e-1 do
begin
x:=(x*m mod n);
end;
cry[i]:=x;
inc(i);

label5.Caption:=label5.Caption+' '+inttostr(x);
end;

end;


procedure TForm1.Button6Click(Sender: TObject);
var x,m,i,t:integer;
begin
i:=1;
while i<= length(s) do
begin
label11.caption:=label11.caption+' '+inttostr(cry[i]);
inc(i);
end;

i:=1;
while i<=length(s) do
begin
x:=cry[i];
m:=x;
for t:=1 to d-1 do
begin
x:=((x*m) mod n);
end;
label8.Caption:=label8.Caption+' '+inttostr(x);
mas[i]:=chr(x);
label9.Caption:=label9.Caption+' '+mas[i];
inc(i);


end;
end;
 


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

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


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