|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
20.01.2010, 17:31 | #1 |
Регистрация: 20.05.2008
Сообщений: 9
|
Здравствуйте, всем!
Вот такая у меня проблема:рабочая программа на тему RSA. Алгоритм заключается в следующем:Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций : 1. Выбираются два простых (!) числа p и q 2. Вычисляется их произведение n(=p*q) 3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1). 4. Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах. 5. Два числа (e,n) – публикуются как открытый ключ. 6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n). Как же производится собственно шифрование с помощью этих чисел : 1. Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа. 2. Подобный блок, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку.операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi. А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y) : (x(-y)(p-1)(q-1))mod n = 1(-y) = 1. Теперь умножим обе ее части на x : (x(-y)(p-1)(q-1)+1)mod n = 1*x = x. А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m : ((ci)d)mod n = ((mi)e*d)mod n = mi. На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла. Моя программа(я считаю) реализует этот алгоритм правильно, НО бывает выбираешь 2 простых числа трехзначными или четырехзначными и ключ е становится =1, либо компьютер просто зависает!Помогите усовершенствовать, может нужно добавить команду, или еще что-н??Я уже не знаю что мне делать вот сама прога Последний раз редактировалось Stilet; 21.01.2010 в 07:49. |
20.01.2010, 20:01 | #2 |
Удален
Форумчанин
Регистрация: 02.12.2009
Сообщений: 309
|
нужно длинную арифметику использовать...
функция для определения простоты числа у вас как-то странно записана. должно быть что-то типо этого: Код:
Последний раз редактировалось Alex_FF; 20.01.2010 в 20:37. |
21.01.2010, 06:36 | #3 |
Регистрация: 20.05.2008
Сообщений: 9
|
Спасибо!Попробую так
Что понимается под "длинной арифметикой"? Последний раз редактировалось Stilet; 21.01.2010 в 09:00. |
21.01.2010, 09:02 | #4 | |
АльTRUEи$т
Форумчанин
Регистрация: 19.03.2009
Сообщений: 784
|
Возможность работать с оооочень большими числами не попадающими не под один из существующих числовых типов языка программирования
Цитата:
|
|
21.01.2010, 09:53 | #5 |
Регистрация: 20.05.2008
Сообщений: 9
|
Скажите, пожалуйста, почему когда рассчитываем ключи иногда d становится равным 1??
Кто-нибудь, помогитЕ!!!;(( Последний раз редактировалось Stilet; 22.01.2010 в 17:09. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
шифрование методом RSA на Delphi | Тёма(C@$pEr) | Помощь студентам | 13 | 17.12.2012 17:42 |
Алгоритм и программа пузырьковой сортировки... | Smagulov85 | Фриланс | 9 | 20.01.2010 23:37 |
криптосистема rsa на delphi | Paul11j | Помощь студентам | 1 | 05.06.2009 20:41 |