Применение алгоритма RSA для шифрования потоков данных
СОДЕРЖАНИЕ
| Введение | 5 |
1.Постановказадачи | 10 |
| 2.Алгоритм RSA | 11 |
| 2.1.Система шифрованияRSA | 12 |
| 2.2.Сложностьтеоретико-числовыхалгоритмов | 16 |
| 2.2.1.Алгоритмвычисления | 17 |
| 2.2.2.Алгоритм Евклида | 18 |
| 2.2.3.Алгоритм решения уравнения | 18 |
| 2.2.4.Алгоритмнахожденияделителеймногочлена в кольце | 21 |
| 3.Качественнаятеория алгоритмаRSA | 23 |
| 3.1. Алгоритм,доказывающий непростотучисла | 24 |
| 3.2.Нахождениебольших простыхчисел | 26 |
| 3.3.Проверка большогочисла на простоту | 30 |
| 4.Практическаяреализацияалгоритма | 37 |
| 4.1.Реализованныеалгоритмы | 37 |
| 4.2.Анализ результатов | 38 |
| 5.Выводы | 39 |
| 5.1Алгоритм | 39 |
| 5.2Алгоритм ипрограмма | 39 |
| Заключение | 41 |
| Списокиспользованныхисточников | 42 |
| Приложение1. Листинг программы | 43 |
| Приложение2. Главная формапрограммы | 46 |
Приложение3. Формабазы данныхабонентов | 47 |
Приложение4. Форманахожденияпростых чисели генерацииключей | 48 |
ВВЕДЕНИЕ
Проблемазащиты информациипутем ее преобразования,исключающегоее прочтениепостороннимлицом, волновалачеловеческийум с давнихвремен. Историякриптографии- ровесницаистории человеческогоязыка. Болеетого, первоначальнописьменностьсама по себебыла своеобразнойкриптографическойсистемой, таккак в древнихобществах еювладели толькоизбранные.Священные книгидревнего Египта,древней Индиитомупримеры.
Историякриптографииусловно можноразделить на4 этапа.
1) наивнаякриптография.
2) формальнаякриптография.
3) научнаякриптография.
4) компьютернаякриптография.
Длянаивнойкриптографии(донач. XVIвека) характерноиспользованиелюбых (обычнопримитивных)способов запутыванияпротивникаотносительносодержанияшифруемыхтекстов.На начальномэтапе для защитыинформациииспользовалисьметоды кодированияистеганографии,которыеродственны,но не тождественныкриптографии.
Большинствоиз используемыхшифров сводилиськ перестановкеилимоноалфавитнойподстановке.Однимиз первыхзафиксированныхпримеров являетсяшифр Цезаря,состоящий взамене каждойбуквы исходноготекста на другую,отстоящую отнее в алфавитена определенноечисло позиций.Другой шифр,полибианскийквадрат, авторствокоторогоприписываетсягреческомуписателю Полибию,является общеймоноалфавитнойподстановкой,которая проводитсяс помощью случайнозаполненнойалфавитомквадратнойтаблицейдлягреческогоалфавита размерсоставляет5x5). Каждая букваисходноготекстазаменяетсяна букву, стоящуюв квадратеснизу от нее.
Этапформальнойкриптографии(кон.XVвека - нач. XXвека)связан с появлениемформализованныхи относительностойкихк ручномукриптоанализушифров. В европейскихстранахэто произошлов эпоху Возрождения,когда развитиенаукии торговливызвало спросна надежныеспособы защитыинформации.Важная рольна этом этапепринадлежитЛеону БатистеАльберти,итальянскомуархитектору,который однимизпервых предложилмногоалфавитнуюподстановку.Данныйшифр, получившийимя дипломатаXVIвека БлезаВижинера, состоялв последовательном«сложении»букв исходноготекста сключом (процедуруможно облегчитьс помощью специальнойтаблицы).Его работа«Трактат ошифре» (1466) считаетсяпервойнаучной работойпо криптологии.
Однойиз первых печатныхработ, в которойобобщены исформулированыизвестные натот моменталгоритмышифрованияявляется труд«Полиграфия»(1508 г.) немецкогоаббата ИоганнаТрисемуса. Емупринадлежатдва небольших,но важныхоткрытия: способзаполненияполибианскогоквадрата (первыепозиции заполняютсяс помощью легкозапоминаемогоключевогослова, остальные- оставшимисябуквами алфавита)и шифрованиепар букв (биграмм).
Простымно стойкимспособоммногоалфавитнойзамены (подстановкибиграмм) являетсяшифр Плейфера,который былоткрытв начале XIXвека ЧарльзомУитстоном.Уитстону принадлежити важное усовершенствование- шифрование«двойнымквадратом».Шифры Плейфераи Уитстонаиспользовалисьвплотьдо первой мировойвойны, так какс трудом поддавалисьручному криптоанализу.
В XIXвеке голландецКеркхоффсформулировалглавное требованиек криптографическимсистемам, котороеостается актуальными поныне: секретностьшифров должнабыть основанана секретностиключа, но неалгоритма.
Наконец,последнимсловом в донаучнойкриптографии,которое обеспечилиеще более высокуюкриптостойкосить,а такжепозволилоавтоматизировать(в смысле механизировать)процессшифрованиястали роторныекриптосистемы.
Однойиз первых подобныхсистем сталаизобретеннаяв 1790 году ТомасомДжефферсоном,будущим президентомСШАмеханическаямашина. Многоалфавитнаяподстановкас помощьюроторной машиныреализуетсявариациейвзаимногоположениявращающихсяроторов, каждыйиз которыхосуществляет«прошитую»в нем подстановку.
Практическоераспространениероторные машиныполучили тольков начале XX века.Одной из первыхпрактическииспользуемыхмашин, сталанемецкая Enigma,разработаннаяв 1917 году ЭдвардомХеберном иусовершенствованнаяАртуром Кирхом.Роторные машиныактивно использовалисьво время второймировой войны.Помимо немецкоймашины Enigma использовалисьтакже устройстваSigaba (США), Турех(Великобритания),Red, Orange и Purple2 (Япония).Роторные системы-вершина формальнойкриптографиитак как относительнопросто реализовывалиочень стойкиешифры. Успешныекриптоатакина роторныесистемы сталивозможны толькос появлениемЭВМ в начале40-х годов.
Главнаяотличительнаячерта научнойкриптографии(30-е - 60-е годы XX века)- появлениекриптосистемсо строгимматематическимобоснованиемкриптостойкости.К началу 30-х годовокончательносформировалисьразделы математики,являющиесянаучной основойкриптологии:теория вероятностейи математическаястатистика,общая алгебра,теория чисел,начали активноразвиватьсятеория алгоритмов,теория информации,кибернетика.Своеобразнымводоразделомстала работаКлода Шеннона«Теория связив секретныхсистемах»(1949), где сформулированытеоретическиепринципыкриптографическойзащиты информации.Шеннон ввелпонятия «рассеивание»и «перемешивание»,обосновалвозможностьсоздания скольугодно стойкихкриптосистем.
В 60-х годахведущие криптографическиешколы подошлик созданиюблочных шифров,еще более стойкихпо сравнениюс роторнымикриптосистемами,однако допускающиепрактическуюреализациютолько в видецифровых электронныхустройств.
Компьютернаякриптография(с 70-х годов XX века)обязана своимпоявлениемвычислительнымсредствам спроизводительностью,достаточнойдля реализациикритосистем,обеспечивающихпри большойскорости шифрованияна несколькопорядков болеевысокую криптостойкость,чем «ручные»и «механические»шифры.
Первымклассом криптосистем,практическоеприменениекоторых сталовозможно споявлениеммощных и компактныхвычислительныхсредств, сталиблочные шифры.В 70-е годы былразработанамериканскийстандарт шифрованияDES(принят в 1978 году).Один из егоавторов, ХорстФейстел (сотрудникIBM),описал модельблочных шифров,на основе которойбыли построеныдругие, болеестойкие симметричныекриптосистемы,в том числеотечественныйстандарт шифрованияГОСТ 28147-89.
С появлениемDESобогатилсяи криптоанализ,для атак наамериканскийалгоритм былсоздано нескольконовых видовкриптоанализа(линейный,дифференциальныйи т.д.), практическаяреализациякоторых опятьже была возможнатолько с появлениеммощных вычислительныхсистем.
В середине70-х годов произошелнастоящийпрорыв в современнойкриптографии- появлениеасимметричныхкриптосистем,которые нетребовалипередачи секретногоключа междусторонами.Здесь отправнойточкой принятосчитать работу,опубликованнуюУитфилдом Диффии МартиномХеллманом в1976 году под названием«Новые направленияв современнойкриптографии».В ней впервыесформулированыпринципы обменашифрованнойинформациейбез обменасекретнымключом. Независимок идее асимметричныхкриптосистемподошел РальфМеркли. Несколькимигодами позжеРон Ривест, АдиШамир и ЛеонардАдлеман открылисистему RSA,первую практическуюасимметричнуюкриптосистему,стойкостькоторой былаоснована напроблеме факторизациибольших простыхчисел. Асимметричнаякриптографияоткрыла сразунесколько новыхприкладныхнаправлений,в частностисистемы электроннойцифровой подписи(ЭЦП) и электронныхденег.
В 80-90-егоды появилисьсовершенноновые направлениякриптографии:вероятностноешифрование,квантоваякриптографияи другие. Осознаниеих практическойценности ещевпереди. Актуальнойостается изадача совершенствованиясимметричныхкриптосистем.В 80-90-х годах былиразработанынефейстеловскиешифры (SAFER,RC6и др.), а в 2000 годупосле открытогомеждународногоконкурса былпринят новыйнациональныйстандарт шифрованияСША - AES.
1. ПОСТАНОВКАЗАДАЧИ
Безопасностьпередачи данныхпо каналамсвязи являетсяактуальной.Современныекомпьютерныесети не исключение.К сожалению,в сетевыхоперационныхсистемах (WindowsNT/XP,Novellи т.д.) иностранногопроизводства,как следствие,из-за экспортныхсоображенийуровень алгоритмовшифрованиязаметно снижен.
Задача:исследоватьсовременныеметоды шифрованияи их приложимостьк шифрованиюпотоков данных.Разработатьсобственнуюбиблиотекуалгоритмовшифрованияи программныйпродукт, демонстрирующийработу этихалгоритмовпри передачеданных в сети.
2.АЛГОРИТМ RSA
Труды Евклидаи Диофанта,Ферма и Эйлера,Гаусса, Чебышеваи Эрмита содержатостроумныеи весьма эффективныеалгоритмырешения диофантовыхуравнений,выясненияразрешимостисравнений,построениябольших по темвременам простыхчисел, нахождениянаилучшихприближенийи т.д. В последниедва десятилетия,благодаря впервую очередьзапросам криптографиии широкомураспространениюЭВМ, исследованияпо алгоритмическимвопросам теориичисел переживаютпериод бурногои весьма плодотворногоразвития.
Вычислительныемашины и электронныесредства связипроникли практическиво все сферычеловеческойдеятельности.Немыслима безних и современнаякриптография.Шифрованиеи дешифрованиетекстов можнопредставлятьсебе как процессыпереработкицелых чиселпри помощи ЭВМ,а способы, которымивыполняютсяэти операции,как некоторыефункции, определённыена множествецелых чисел.Всё это делаетестественнымпоявление вкриптографииметодов теориичисел. Крометого, стойкостьряда современныхкриптосистемобосновываетсятолько сложностьюнекоторыхтеоретико-числовыхзадач.
Но возможностиЭВМ имеютопределённыеграницы. Приходитсяразбиватьдлинную цифровуюпоследовательностьна блоки ограниченнойдлины и шифроватькаждый такойблок отдельно.Мы будем считатьв дальнейшем,что все шифруемыецелые числанеотрицательныи по величинеменьше некоторогозаданного(скажем, техническимиограничениями)числа m.Таким же условиямбудут удовлетворятьи числа, получаемыев процессешифрования.Это позволяетсчитать и те,и другие числаэлементамикольца вычетов
.Шифрующаяфункция приэтом можетрассматриватьсякак взаимнооднозначноеотображениеколец вычетов 
а число
представляетсобой сообщение 
в зашифрованномвиде.Простейшийшифр такогорода - шифр замены,соответствуетотображению
при некоторомфиксированномцелом k.Подобный шифриспользовалеще Юлий Цезарь.Конечно, некаждое отображение 
подходит дляцелей надежногосокрытия информации.В 1978 г. американцыР. Ривест, А. Шамири Л. Адлеман(R.L.Rivest.A.Shamir.L.Adleman)предложилипример функции
,обладающейрядом замечательныхдостоинств.На её основебыла построенареально используемаясистема шифрования,получившаяназвание попервым буквамимен авторов-система RSA.Эта функциятакова, что1)существуетдостаточнобыстрый алгоритмвычислениязначений
;2)существуетдостаточнобыстрый алгоритмвычислениязначений обратнойфункции
;3)функция
обладает некоторым«секретом»,знание которогопозволяетбыстро вычислятьзначения ;в противномже случае вычисление становитсятрудно разрешимойв вычислительномотношениизадачей, требующейдля своегорешения стольмного времени,что по егопрошествиизашифрованнаяинформацияперестаетпредставлятьинтерес длялиц, использующихотображение
в качествешифра.Еще до выходаиз печати статьикопия докладав МассачусетскомТехнологическоминституте,посвящённогосистеме RSA.была посланаизвестномупопуляризаторуматематикиМ. Гарднеру,который в 1977 г.в журнале ScientificAmericanопубликовалстатью посвящённуюэтой системешифрования.В русском переводезаглавие статьиГарднера звучиттак: Новый видшифра, на расшифровкукоторого потребуютсямиллионы лет.Именно этастатья сыгралаважнейшую рольв распространенииинформацииоб RSA,привлекла ккриптографиивнимание широкихкругов неспециалистови фактическиспособствовалабурному прогрессуэтой области,произошедшемув последовавшие20 лет.
2.1. системашифрованияRSA
Пусть
и 
натуральныечисла. Функция реализующаясхему RSA,устроена следующимобразом
. (1)Для расшифровкисообщения
достаточнорешить сравнение
. (2)При некоторыхусловиях на
и это сравнениеимеет единственноерешение .Для того,чтобы описатьэти условияи объяснить,как можно найтирешение, нампотребуетсяодна теоретико-числоваяфункция, такназываемаяфункция Эйлера.Эта функциянатуральногоаргумента
обозначается 
и равняетсяколичествуцелых чиселна отрезке от1 до ,взаимно простыхс .Так 
и 
для любогопростого числа 
и натурального 
.Кроме того, 
для любыхнатуральныхвзаимно простых 
и 
.Эти свойствапозволяют легковычислитьзначение ,если известноразложениечисла на простыесомножители.Если показательстепени
в сравнении(2) взаимно простс ,то сравнение(2) имеет единственноерешение. Длятого, чтобынайти его, определимцелое число 
,удовлетворяющееусловиям
. (3)Такое числосуществует,поскольку
,и притом единственно.Здесь и далеесимволом 
будет обозначатьсянаибольшийобщий делительчисел и .Классическаятеорема Эйлера,утверждает,что для каждогочисла ,взаимно простогос ,выполняетсясравнение 
и, следовательно.
. (4)Такимобразом, впредположении
,единственноерешение сравнения(2) может бытьнайдено в виде
. (5)Если дополнительнопредположить,что число
состоит изразличныхпростых сомножителей,то сравнение(5) будет выполнятьсяи без предположения .Действительно,обозначим 
и 
.Тогда делится на 
,а из (2) следует,что 
.Подобно (4), теперьлегко находим 
.А кроме того,имеем 
.Получившиесясравнения всилу 
дают нам (5).Функция(1), принятая всистеме RSA,может бытьвычисленадостаточнобыстро. Обратнаяк
функция 
вычисляетсяпо тем же правилам,что и ,лишь с заменойпоказателястепени на .Таким образом,для функции(1) будут выполненыуказанные вышесвойства 1) и2).Для вычисленияфункции (1) достаточнознать лишьчисла
и .Именно онисоставляютоткрытый ключдля шифрования.А вот для вычисленияобратной функциитребуется знатьчисло .оно и является«секретом»,о котором речьидёт в пунктев). Казалосьбы. ничего нестоит. знаячисло .разложить егона простыесомножители,вычислить затемс помощью известныхправил значение и, наконец, спомощью (3) определитьнужное число .Все шаги этоговычислениямогут бытьреализованыдостаточнобыстро, заисключениемпервого. Именноразложениечисла на простыемножители исоставляетнаиболее трудоемкуючасть вычислений.В теории чиселнесмотря намноголетнююеё историю ина очень интенсивныепоиски в течениепоследних 20лет, эффективныйалгоритм разложениянатуральныхчисел на множителитак и не найден.Конечно, можно,перебирая всепростые числадо 
,и. деля на них ,найти требуемоеразложение.Но, учитывая,что количествопростых в этомпромежутке,асимптотическиравно 
,находим, чтопри ,записываемом100 десятичнымицифрами, найдётсяне менее 
простых чисел,на которыепридётся делить при разложенииего на множители.Очень грубыеприкидки показывают,что компьютеру,выполняющемумиллион деленийв секунду, дляразложениячисла 
таким способомна простыесомножителипотребуетсяне менее, чем 
лет. Известныи более эффективныеспособы разложенияцелых чиселна множители,чем простойперебор простыхделителей, нои они работаюточень медленно.Авторысхемы RSAпредложиливыбирать число
в виде произведениядвух простыхмножителей и 
,примерно одинаковыхпо величине.Так как
, (6)то единственноеусловие навыбор показателястепени
в отображении(1) есть
. (7)Итак, лицо,заинтересованноев организациишифрованнойпереписки спомощью схемыRSA,выбирает двадостаточнобольших простыхчисла
и .Перемножаяих, оно находитчисло 
.Затем выбираетсячисло ,удовлетворяющееусловиям (7),вычисляетсяс помощью (6) число и с помощью (3)- число .Числа и публикуются,число остается секретным.Теперь любойможет отправлятьзашифрованныес помощью (1)сообщенияорганизаторуэтой системы,а организаторлегко сможетрасшифровыватьих с помощью(5).Для иллюстрациисвоего методаРивест, Шамири Адлеманзашифровалитаким способомнекоторуюанглийскуюфразу. Сначалаона стандартнымобразом (а=01, b=02,.... z=26,пробел=00) былазаписана в видецелого числа
,а затем зашифрованас помощью отображения(1) приm=114381625757888867669325779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
и
.Эти два числабыли опубликованы,причем дополнительносообщалось,что .где и - простые числа,записываемыесоответственно64 и 65 десятичнымизнаками. Первому,кто расшифруетсоответствующеесообщение 
,была обещананаграда в 100$.
Эта историязавершиласьспустя 17 лет в1994 г., когда D.Atkins,M.Graff,А. К. Lenstraи Р. С. Leylandсообщили орасшифровкефразы. Числа
и оказалисьравными 
, 
.Этот замечательныйрезультат(разложениена множители129-значногодесятичногочисла) был достигнутблагодаряиспользованиюалгоритмаразложениячисел на множители,называемогометодом квадратичногорешета. Выполнениевычисленийпотребовалоколоссальныхресурсов. Вработе, возглавлявшейсячетырьмя авторамипроекта, ипродолжавшейсяпосле предварительнойтеоретическойподготовкипримерно 220 дней,на добровольныхначалах участвовалооколо 600 человеки примерно 1600компьютеров,объединённыхсетью Internet.Наконец, отметим,что премия в100$ была переданав FreeSoftwareFoundation.
2.2.Сложностьтеоретико-числовыхалгоритмов
Сложностьалгоритмовтеории чиселобычно принятоизмерять количествомарифметическихопераций (сложений,вычитаний,умножений иделений с остатком),необходимыхдля выполнениявсех действий,предписанныхалгоритмом.Впрочем, этоопределениене учитываетвеличины чисел,участвующихв вычислениях.Ясно, что перемножитьдва стозначныхчисла значительносложнее, чемдва однозначных,хотя при этоми в том, и в другомслучае выполняетсялишь однаарифметическаяоперация.Поэтому иногдаучитывают ещёи величинучисел, сводядело к так называемымбитовым операциям,т. е. оцениваяколичествонеобходимыхопераций сцифрами 0 и 1, вдвоичной записичисел.
Говоряо сложностиалгоритмов,мы будем иметьв виду количествоарифметическихопераций. Припостроенииэффективныхалгоритмови обсужденииверхних оценоксложностиобычно хватаетинтуитивныхпонятий тойобласти математики,которой принадлежиталгоритм.Формализацияже этих понятийтребуется лишьтогда, когдаречь идёт оботсутствииалгоритма илидоказательственижних опеноксложности.
Приведемтеперь примерыдостаточнобыстрых алгоритмовс опенкамиих сложности.Здесь и в дальнейшеммы не будемпридерживатьсяформальногоописания алгоритмов,стараясь впервую очередьобъяснить смыслвыполняемыхдействий.
Следующийалгоритм вычисляет
за 
арифметическихопераций. Приэтом, конечно,предполагается,что натуральныечисла и не превосходятпо величине .2.2.1.Алгоритмвычисления
-
Представим
в двоичнойсистеме счисления 
,где 
,цифры в двоичномпредставлении,равны 0 или 1, 
. -
Положим
и затем для 
вычислим
.3)
есть искомыйвычет .Справедливостьэтого алгоритмавытекает изсравнения
,легкодоказываемогоиндукцией по
.Так каккаждое вычислениена шаге 2 требуетне более трёхумноженийпо модулю
и этот шагвыполняется 
раз, то сложностьалгоритма можетбыть оцененавеличиной .Второйалгоритм - этоклассическийалгоритм Евклидавычислениянаибольшегообщего делителяцелых чисел.Мы предполагаемзаданными дванатуральныхчисла
и и вычисляемих наибольшийобщий делитель 
.2.2.2.АлгоритмЕвклида
-
Вычислим
- остаток отделения числа на , 
, 
. -
Если
,то есть искомоечисло. -
Если
,то заменимпару чисел 
парой 
и перейдемк
шагу 1.
Теорема1. При вычислениинаибольшегообщего делителя
с помощью алгоритмаЕвклида будетвыполнено неболее 
операций деленияс остатком, где есть количествоцифр в десятичнойзаписи меньшегоиз чисел и .Доказательство.Положим
и определим 
- последовательностьделителей,появляющихсяв процессевыполненияшага 1 алгоритмаЕвклида. Тогда 
.Пусть также
, 
, 
, 
,- последовательностьФибоначчи.Индукцией по от 
до 
легко доказываетсянеравенство 
.А так как 
,то имеем неравенства 
и 
.Немногоподправивалгоритм Евклида,можно достаточнобыстро решатьсравнения
при условии,что 
.Эта задачаравносильнапоиску целыхрешений уравнения 
.2.2.3.Алгоритм решения уравнения
0) Определимматрицу
.1) Вычислим
- остаток отделения числа на , , .-
Если
,то второй столбецматрицы 
даёт вектор 
решенийуравнения. -
Если
,то заменимматрицу матрицей 
. -
Заменимпару чисел
парой и перейдем кшагу 1.
Если обозначитьчерез
матрицу ,возникающуюв процессеработы алгоритмаперед шагом2 после 
делений с остатком(шаг 1), то в обозначенияхиз доказательстватеоремы 1 в этотмомент выполняетсявекторноеравенство 
.Поскольку числа и взаимно просты,имеем 
,и это доказывает,что алгоритмдействительнодаёт решениеуравнения .Буквой 
мы обозначиликоличестводелений с остатком,которое в точноститакое же, каки в алгоритмеЕвклида.Три приведённыхвыше алгоритмаотносятся кразряду такназываемыхполиномиальныхалгоритмов.Это названиеносят алгоритмы,сложностькоторых оцениваетсясверху степеннымобразом в зависимостиот длины записивходящих чисел.Если наибольшееиз чисел, подаваемыхна вход алгоритма,не превосходит
,то сложностьалгоритмовэтого типаоцениваетсявеличиной 
,где 
- некотораяабсолютнаяпостоянная.Во всех приведённыхвыше примерах 
.Полиномиальныеалгоритмы втеории чисел- большая редкость.Да и опенкисложностиалгоритмовчаше всегоопираются накакие-либо недоказанные,но правдоподобныегипотезы, обычноотносящиесяк аналитическойтеории чисел.
Для некоторыхзадач эффективныеалгоритмывообще не известны.Иногда в такихслучаях всеже можно предложитьпоследовательностьдействий, которая,«если повезет»,быстро приводитк требуемомурезультату.Существуеткласс так называемыхвероятностныхалгоритмов,которые даютправильныйрезультат, ноимеют вероятностнуюопенку времениработы. Обычноработа этихалгоритмовзависит отодного илинесколькихпараметров.В худшем случаеони работаютдостаточнодолго. Ноудачный выборпараметраопределяетбыстрое завершениеработы. Такиеалгоритмы, еслимножество«хороших»значений параметроввелико, на практикеработают достаточноэффективно,хотя и не имеютхороших опеноксложности.
Мы будеминогда использоватьслова детерминированныйалгоритм, чтобыотличать алгоритмыв обычном смыслеот вероятностныхалгоритмов.
Как пример,рассмотримвероятностныйалгоритм, позволяющийэффективнонаходить решенияполиномиальныхсравнений попростому модулю.Пусть
— простое число,которое предполагаетсябольшим, и 
- многочлен,степень которогопредполагаетсяограниченной.Задача состоитв отысканиирешений сравнения
. (8)Например,речь может идтио решенииквадратичныхсравнений, еслистепень многочлена
равна 2. Другимисловами, мыдолжны отыскатьв поле 
все элементы,удовлетворяющиеуравнению 
.Согласномалой теоремеФерма, все элементыполя
являютсяоднократнымикорнями многочлена 
.Поэтому, вычисливнаибольшийобщий делитель 
,мы найдем многочлен 
,множествокорней которогов поле совпадает смножествомкорней многочлена ,причем все этикорни однократны.Если окажется,что многочлен имеет нулевуюстепень, т. е.лежит в поле ,это будет означать,что сравнение(8) не имеет решений.Для вычислениямногочлена
удобно сначалавычислитьмногочлен 
,пользуясьалгоритмом,подобным описанномувыше алгоритмувозведенияв степень (напомним,что число предполагаетсябольшим). А затемс помощью аналогаалгоритмаЕвклида вычислить 
.Всё это выполняетсяза полиномиальноеколичествоарифметическихопераций.Такимобразом, обсуждаядалее задачунахождениярешений сравнения(8), мы можем предполагать,что в кольцемногочленов
справедливоравенство 
2.2.4.Алгоритм нахожденияделителеймногочлена
в кольце 1)Выберемкаким-либоспособом элемент
.-
Вычислимнаибольшийобщий делитель
. -
Если многочлен
окажется собственнымделителем ,то многочлен распадётсяна два множителяи с каждым изних независимонужно будетпроделать всеоперации,предписываемыенастоящималгоритмомдля многочлена .
4) Если окажется,что
или 
,следует перейтик шагу 1 и. выбравновое значение 
,продолжитьвыполнениеалгоритма.Количествоопераций нашаге 2 оцениваетсявеличиной
,если вычисленияпроводить так,как это указывалосьвыше при нахождении .Выясним теперь,сколь долгопридётся выбиратьчисла ,пока на шаге2 не будет найденсобственныйделитель .Количестворешений уравнения
в поле не превосходит 
.Это означает,что подмножество 
элементов ,удовлетворяющихусловиям 
,состоитне менее, чемиз
элементов.Учитывая теперь,что каждыйненулевойэлемент 
удовлетворяетодному из равенств 
,либо 
,заключаем, чтодля 
одно из чисел 
будет корнеммногочлена 
,а другое - нет.Для таких элементов многочлен ,определённыйна шаге 2 алгоритма,будет собственнымделителеммногочлена .Итак, существуетне менее
«удачных»выборов элемента ,при которыхна шаге 2 алгоритмамногочлен распадётсяна два собственныхмножителя.Следовательно,при «случайном»выборе элемента ,вероятностьтого, что многочленне разложитсяна множителипосле повторенийшагов алгоритма1-4. не превосходит 
.Вероятностьс ростом убывает оченьбыстро. И действительно,на практикеэтот алгоритмработает достаточноэффективно.Заметим,что при опенкевероятностимы использовалитолько двакорня многочлена
.При 
эта вероятность,конечно, ещеменьше. Болеетонкий анализс использованиемопенок А. Вейлядля сумм характеровпоказывает,что вероятностьдля многочлена не распастьсяна множителипри однократномпроходе шаговалгоритма 1-4.не превосходит 
.Здесь постояннаяв 
зависит от .Если всравнении (8)заменить простоймодуль
составныммодулем ,то задача нахождениярешений соответствующегосравнениястановитсянамного болеесложной. Известныеалгоритмы еёрешения основанына сведениисравнения ксовокупностисравнений (8)по простыммодулям — делителям ,и. следовательно,они требуютразложениячисла то напростые сомножители,что, как ужеуказывалось,является достаточнотрудоемкойзадачей.3.КАЧЕСТВЕННАЯТЕОРИЯ АЛГОРИТМАRSA
Существуетдовольно эффективныйспособ убедиться,что заданноечисло являетсясоставным, неразлагая эточисло на множители.Согласно малойтеореме Ферма,если число
простое, то длялюбого целого ,не делящегосяна ,выполняетсясравнение
. (9)Если жепри каком-то
это сравнениенарушается,можно утверждать,что - составное.Проверка (9) нетребует большихвычислений,это следуетиз алгоритма1. Вопрос тольков том, как найтидля составного целое число ,не удовлетворяющее(9). Можно, например,пытаться найтинеобходимоечисло ,испытывая всецелые числаподряд, начинаяс 2. Или попробоватьвыбирать этичисла случайнымобразом наотрезке 
.К сожалению,такой подходне всегда даётто, что хотелосьбы. Имеютсясоставные числа
,обладающиесвойством (9)для любогоцелого с условием 
.Такие числаназываютсячислами Кармайкла.Рассмотрим,например, число 
.Так как 560 делитсяна каждое изчисел 2, 10, 16, то спомощью малойтеоремы Фермалегко проверить,что 561 есть числоКармайкла.Можно доказать,что любое изчисел Кармайклаимеет вид 
,где все простые 
различны, причем 
делится накаждую разность 
.Лишь недавно,была решенапроблема обесконечностимножества такихчисел.В 1976 г. Миллерпредложилзаменить проверку(9) проверкойнесколькоиного условия.Если
- простое число, 
,где 
нечётно, тосогласно малойтеореме Фермадля каждого с условием хотя бы однаиз скобок впроизведении 
делитсяна
.Обращение этогосвойства можноиспользовать,чтобы отличатьсоставные числаот простых.Пусть
- нечётное составноечисло, ,где нечётно. Назовемцелое число , ,«хорошим» для ,если нарушаетсяодно из двухусловий: 1)
не делится на ;2)
или существуетцелое , 
,такое, что 
.Из сказанногоранее следует,что для простогочисла
не существуетхороших чисел .Если же составноечисло, то, какдоказал Рабин,их существуетне менее 
.Теперь можнопостроитьвероятностныйалгоритм, отличающийсоставныечисла от простых.
3.1. Алгоритм,доказывающий непростотучисла
-
Выберемслучайнымобразом число
, ,и проверимдля
этого числауказанные вышесвойства 1) и2) п.2. -
Если хотябы одно из нихнарушается,то число
составное. Если выполненыоба условия1) и 2) п.2, возвращаемсяк шагу 1.
Из сказанноговыше следует,что составноечисло не будетопределенокак составноепосле однократноговыполненияшагов 1-3 с вероятностьюне большей
.А вероятностьне определитьего после повторенийне превосходит 
.т. е. убываеточень быстро.Миллерпредложилдетерминированныйалгоритм определениясоставныхчисел, имеющийсложность
,однако справедливостьего результатазависит отнедоказаннойв настоящеевремя так называемойрасширеннойгипотезы Римана.Согласно этомуалгоритмудостаточнопроверитьусловия 1) и 2) п.2для всех целыхчисел , 
.Если при каком-нибудь из указанногопромежутканарушаетсяодно из условийа) или б), число составное. Впротивномслучае онобудет простымили степеньюпростого числа.Последняявозможность,конечно, легкопроверяется.Напомнимнекоторыепонятия, необходимыедля формулировкирасширеннойгипотезы Римана.Они понадобятсянам и в дальнейшем.Пусть
- целое число.Функция 
называетсяхарактеромДирихле помодулю ,или простохарактером,если эта функцияпериодичнас периодом ,отлична от нулятолько на числах,взаимно простыхс ,и мультипликативна,т. е. для любыхцелых 
выполняетсяравенство 
.Для каждого существуетровно характеровДирихле. Ониобразуют группупо умножению.Единичнымэлементом этойгруппы являетсятак называемыйглавный характер 
,равный 1 на всехчислах, взаимнопростых с ,и 0 на остальныхцелых числах.Порядком характераназываетсяего порядоккак элементамультипликативнойгруппы характеров.С каждымхарактеромможет бытьсвязана такназываемая
- функция Дирихле- функция комплексногопеременного 
,определённаярядом 
.Сумма этогоряда аналитичнав области 
и может бытьаналитическипродолженана всю комплекснуюплоскость.Следующеесоотношение 
связывает L- функцию, отвечающуюглавному характеру,с дзета-функцией Римана 
.Расширеннаягипотеза Риманаутверждает,что комплексныенули всех L-функций Дирихле,расположенныев полосе 
,лежат на прямой 
.В настоящеевремя не доказанадаже простейшаяформа этойгипотезы -классическаягипотеза Римана,утверждающаятакой же факто нулях дзета-функции.В 1952 г. Анкенис помощью расширеннойгипотезы Риманадоказал, чтодля каждогопростого числа
существуетквадратичныйневычет ,удовлетворяющийнеравенствам 
.Константа 70была сосчитанапозднее. Именноэто утверждениеи лежит в основеалгоритмаМиллера. В 1957 г.Берджесс доказалсуществованиетакого невычетабез использованиярасширеннойгипотезы Римана,но с худшейоценкой 
,справедливойпри любомположительном 
и ,большем некоторойграницы, зависящейот .АлгоритмМиллера принципиальноотличаетсяот алгоритма2.1., так как полученноес его помощьюутверждениео том, что число
- составное,опирается нанедоказаннуюрасширеннуюгипотезу Риманаи потому можетбыть неверным.В то время каквероятностныйалгоритм 2.1. даётсовершенноправильныйответ для составныхчисел. Несмотряна отсутствиеоценок сложности,на практикеон работаетвполне удовлетворительно.3.2.Нахождениебольших простыхчисел
Конечноже, большиепростые числаможно строитьсравнительнобыстро. Приэтом можнообеспечитьих случайноераспределениев заданномдиапазоневеличин. В противномслучае терялабы всякийпрактическийсмысл системашифрованияRSA.Наиболее эффективнымсредствомпостроенияпростых чиселявляется несколькомодифицированнаямалая теоремаФерма.
Теорема2. Пусть
- нечётныенатуральныечисла, 
,причем длякаждого простогоделителя числа 
существуетцелое число такое, что 
.(10)Тогда каждыйпростой делитель
числа удовлетворяетсравнению 
.Доказательство.Пусть
- простой делительчисла ,a - некоторыйделитель .Из условий (10)следует, чтов поле вычетов 
справедливысоотношения
. (11)Обозначимбуквой
порядок элемента в мультипликативнойгруппе поля .Первые два изсоотношений(11) означают, что входит в разложениена простыемножители числа в степени такойже, как и в разложение ,а последнее- что 
делится на .Таким образом,каждый простойделитель числа входит в разложение в степени неменьшей, чемв ,так что делится на .Кроме того, четно. Теорема2 доказана.Следствие.Если выполненыусловия теоремы2 и
,то - простое число.Действительно,пусть
равняетсяпроизведениюне менее двухпростых чисел.Каждое из них,согласно утверждениютеоремы 2, неменьше, чем 
.Но тогда 
.Противоречиеи доказываетследствие.Покажемтеперь, как спомощью последнегоутверждения,имея большоепростое число
,можно построитьсущественнобольшее простоечисло .Выберем дляэтого случайнымобразом чётноечисло 
на промежутке 
и положим 
.Затем проверимчисло на отсутствиемалых простыхделителей,разделив егона малые простыечисла; испытаем некотороеколичествораз с помощьюалгоритма 5.Если при этомвыяснится, что - составноечисло, следуетвыбрать новоезначение и опять повторитьвычисления.Так следуетделать до техпор, пока небудет найденочисло ,выдержавшееиспытанияалгоритмом5 достаточномного раз. Вэтом случаепоявляетсянадежда на то,что - простое число,и следует попытатьсядоказать простотус помощью тестовтеоремы 2.Для этогоможно случайнымобразом выбиратьчисло
,и проверятьдля него выполнимостьсоотношений
. (12)Если привыбранном
эти соотношениявыполняются,то, согласноследствиюиз теоремы 2,можно утверждать,что число простое. Еслиже эти условиянарушаются,нужно выбратьдругое значение и повторятьэти операциидо тех пор, покатакое числоне будет обнаружено.Предположим,что построенноечисло
действительноявляется простым.Зададимсявопросом, скольдолго придётсяперебиратьчисла ,пока не будетнайдено такое,для которогобудут выполненыусловия (12). Заметим,что для простогочисла первое условие(12), согласно малойтеореме Ферма,будет выполнятьсявсегда. Те жечисла ,для которыхнарушаетсявторое условие(12), удовлетворяютсравнению 
.Как известно,уравнение 
в поле вычетов 
имеет не более решений. Одноиз них 
.Поэтому напромежутке имеется неболее 
чисел, для которыхне выполняютсяусловия (12). Этоозначает, что,выбирая случайнымобразом числа на промежутке ,при простом можно с вероятностьюбольшей, чем 
,найти число ,для которогобудут выполненыусловия теоремы2, и тем доказать,что действительноявляется простымчислом.Заметим,что построенноетаким способомпростое число
будет удовлетворятьнеравенству 
,т. е. будет записыватьсявдвое большимколичествомцифр, чем исходноепростое число .Заменив теперьчисло на найденноепростое число и повторив сэтим новым все указанныевыше действия,можно построитьеще большеепростое число.Начав с какого-нибудьпростого числа,скажем, записанного10 десятичнымицифрами (простотуего можно проверить,например, делениемна маленькиетабличныепростые числа),и повторивуказаннуюпроцедурудостаточноечисло раз. можнопостроитьпростые числанужной величины.Обсудимтеперь некоторыетеоретическиевопросы, возникающиев связи с нахождениемчисла
,удовлетворяющегонеравенствам ,и такого, что - простое число.Прежде всего,согласно теоремеДирихле, доказаннойеще в 1839 г., прогрессия 
, 
содержит бесконечноеколичествопростых чисел.Нас интересуютпростые числа,лежащие недалекоот начала прогрессии.Опенка наименьшегопростого числав арифметическойпрогрессиибыла полученав 1944 г. Ю. В. Линником.Соответствующаятеорема утверждает,что наименьшеепростое числов арифметическойпрогрессии не превосходит 
,где 
- некотораядостаточнобольшая абсолютнаяпостоянная.Такимобразом, в настоящеевремя никакихтеоретическихгарантий длясуществованияпростого числа
не существует.Тем не менееопыт вычисленийна ЭВМ показывает,что простыечисла в арифметическойпрогрессиивстречаютсядостаточноблизко к еёначалу. Упомянемв этой связигипотезу осуществованиибесконечногоколичествапростых чисел с условием, чточисло 
также простое,т. е. простымявляется ужепервый членпрогрессии.Очень важенв связи с описываемымметодом построенияпростых чиселтакже вопросо расстояниимежду соседнимипростыми числамив арифметическойпрогрессии.Ведь убедившись,что при некотором
число составное,можно следующеезначение взять равным 
и действоватьтак далее, покане будет найденопростое число .И если расстояниемежду соседнимипростыми числамив прогрессиивелико, нетнадежды быстропостроитьнужное число .Перебор чисел до того момента,как мы наткнемсяна простоечисло окажется слишкомдолгим. В болеепростом вопросео расстояниимежду соседнимипростыми числами 
и 
в натуральномряде доказанолишь, что 
,что, конечно,не очень хорошодля наших целей.Вместе с темсуществуеттак называемаягипотеза Крамера(1936 г.), что 
,дающая вполнеприемлемуюопенку. Примернотакой же результатследует и израсширеннойгипотезы Римана.Вычисленияна ЭВМ показывают,что простыечисла в арифметическихпрогрессияхрасположеныдостаточноплотно.В качествеитога обсужденияв этом пунктеподчеркнёмследующее: еслипринять наверу, что наименьшеепростое число,а также расстояниемежду соседнимипростыми числамив прогрессии
при 
оцениваютсявеличиной 
,то описаннаясхема построениябольших простыхчисел имеетполиномиальнуюопенку сложности.Кроме того,несмотря наотсутствиетеоретическихопенок времениработы алгоритмов,отыскивающихпростые числав арифметическихпрогрессияхсо сравнительнобольшой разностью,на практикеэти алгоритмыработают вполнеудовлетворительно.На обычномперсональномкомпьютеребез особыхзатрат временистроятся такимспособом простыечисла порядка 
.Конечно,способ конструированияпростых чиселдля использованияв схеме RSAдолжен бытьмассовым, асами простыечисла должныбыть в каком-тосмысле хорошораспределёнными.Это вносит ряддополнительныхосложненийв работу алгоритмов.
Наконец,отметим, чтосуществуютметоды построениябольших простыхчисел, использующиене только простыеделители
,но и делителичисел 
.В основе ихлежит использованиепоследовательностейцелых чисел,удовлетворяющихлинейным рекуррентнымуравнениямразличныхпорядков. Отметим,что последовательность 
,члены которойприсутствуютв формулировкемалой теоремыФерма, составляетрешение рекуррентногоуравненияпервого порядка 
.3.3. Проверкабольшого числана простоту
Есть некотороеотличие в постановкахзадач предыдущегои настоящегопунктов. Когдамы строим простоечисло
,мы обладаемнекоторойдополнительнойинформациейо нем, возникающейв процессепостроения.Например, такойинформациейявляется знаниепростых делителейчисла .Эта информацияиногда облегчаетдоказательствопростоты .В этом пунктемы предполагаемлишь, что намзадано некотороечисло
,например, выбранноеслучайнымобразом накаком-то промежутке,и требуетсяустановитьего простоту,или доказать,что оно являетсясоставным. Этузадачу заполиномиальноеколичествоопераций решаетуказанный вп. 3 алгоритмМиллера. Однако,справедливостьполученногос его помощьюутверждениязависит отнедоказаннойрасширеннойгипотезы Римана.Если число выдержалоиспытанияалгоритмом5 для 100 различныхзначений параметра ,то, по-видимому,можно утверждать,что оно являетсяпростым свероятностьюбольшей, чем 
.Эта вероятностьочень близкак единице, однаковсё же оставляетнекоторую теньсомнения напростоте числа .В дальнейшемв этом пунктемы будем считать,что заданноечисло является простым,а нам требуетсялишь доказатьэто.В настоящеевремя известныдетерминированныеалгоритмыразличнойсложности длядоказательствапростоты чисел.Мы остановимсяподробнеена одном изних, предложенномв 1983 г. в совместнойработе Адлемана.Померанца иРамели. Длядоказательствапростоты илинепростотычисла
этот алгоритмтребует 
арифметическихопераций. Здесь - некотораяположительнаяабсолютнаяпостоянная.Функция 
хоть и медленно,но всё же возрастаетс ростом ,поэтому алгоритмне являетсяполиномиальным.Но всё же егопрактическиереализациипозволяютдостаточнобыстро тестироватьчисла на простоту.Существенныеусовершенствованияи упрощенияв первоначальныйвариант алгоритмабыли внесеныв работах X.Ленстры и А.Коена. Мы будемназывать описываемыйниже алгоритмалгоритмомАдлемана - Ленстры.В основеалгоритма лежитиспользованиесравнений типамалой теоремыФерма, но в кольцахцелых чиселкруговых полей,т. е. полей. порождённыхнад полем
числами 
- корнями из 1.Пусть - простое нечётноечисло и — первообразныйкорень по модулю ,т. е. образующийэлемент мультипликативнойгруппы поля 
,которая пиклична.Для каждогоцелого числа ,не делящегосяна ,можно определитьего индекс, 
,называемыйтакже дискретнымлогарифмом,с помощью сравнения 
.Рассмотримдалее два простыхчисла , с условием, что 
делится на ,но не делитсяна 
.Следующаяфункция, определённаяна множествецелых чисел.
являетсяхарактеромпо модулю
и порядок этогохарактера равен .Сумма
называетсясуммой Гаусса.Формулируемаяниже теорема3 представляетсобой аналогмалой теоремыФерма, используемыйв алгоритмеАдлемана - Ленстры.
Теорема3. Пусть
- нечетное простоечисло, 
.Тогда в кольце 
выполняетсясравнение 
.Если прикаких-либочислах
сравнение изтеоремы 3 нарушается.можно утверждать,что составноечисло. В противномслучае, еслисравнениевыполняется,оно даёт некоторуюинформациюо возможныхпростых делителяхчисла .Собрав такуюинформациюдля различных 
,в конце концовудаётся установить,что имеет лишь одинпростой делительи являетсяпростым.В случае
легко проверить,что сравнениеиз теоремы 3равносильнохорошо известномув элементарнойтеории чиселсравнению 
,(13)где
- так называемыйсимвол Якоби.Хорошо известнотакже, что последнеесравнениевыполняетсяне только дляпростых ,но и для любыхцелых ,взаимно простыхс .Заметим также,что для вычислениясимвола Якобисуществуетбыстрый алгоритм,основанныйна законе взаимностиГаусса и. в некоторомсмысле, подобныйалгоритмуЕвклида вычислениянаибольшегообщего делителя.Следующийпример показывает.каким образомвыполнимостьнесколькихсравнений типа(13) даёт некоторуюинформациюо возможныхпростых делителяхчисла .Пример(X.Ленстра). Пусть
— натуральноечисло, 
.для котороговыполненысравнения
, (14)а крометого с некоторымцелым числом
имеем
. (15)Как ужеуказывалось,при простом
сравнения (14)выполняютсядля любого ,взаимно простогос ,а сравнение(15) означает, что есть первообразныйкорень по модулю .Количествопервообразныхкорней равно 
,т. е. достаточновелико. Такимобразом, число с условием(15) при простом может бытьнайдено достаточнобыстро с помощьюслучайноговыбора и последующейпроверки (15).Докажем,что из выполнимости(14-15) следует, чтокаждый делитель
числа удовлетворяетодному из сравнений
или 
. (16)Не уменьшаяобщности, можносчитать, что
- простое число.Введем теперьобозначения 
,где 
и 
- нечётные числа.Из (15) и сравнения 
следует, что 
.Далее, согласно(14). выполняютсяследующиесравнения 
,означающие(в силу того,что символЯкоби можетравняться лишь-1 или +1), что
.При
это равенствоозначает, что 
при 
,и, следовательно, .Если же 
,то имеем 
и .Этим (16) доказано.Информациятакого родаполучаетсяи в случаепроизвольныхпростых чисел
и с указаннымивыше свойствами.Опишемсхему алгоритмаАдлемана - Ленстрыдля проверкипростоты
:1)выбираютсяразличныепростые числа
и различныепростые нечётные 
такие, что1)для каждого
все простыеделители числа 
содержатсясреди
и не делятся наквадрат простогочисла;1)
.-
для каждойпары выбранныхчисел
, проводятсятесты, подобныесравнению изтеоремы 3. Если не удовлетворяеткакому-либоиз
этих тестов- оно составное.В противномслучае -
определяетсяне очень большоемножествочисел, с которымитолько и могутбыть сравнимыпростые делители
.А именно, каждыйпростой делитель числа должен удовлетворятьсравнению вида
, 
.4)проверяется,содержит линайденноемножестводелители
.Если при этомделители необнаружены,утверждается,что - простоечисло.
Если число
составное, онообязательноимеет простойделитель ,меньший 
,который самсодержитсясреди возможныхостатков. Именнона этом свойствеосновано применениепункта 4) алгоритма.Сумма Якоби
определяетсядля двух характеров
модулю .Если характерыимеют порядок ,то соответствующаясумма Якобипринадлежиткольцу 
.Поскольку числа ,участвующиев алгоритме,сравнительноневелики, товычисленияс суммами Якобипроизводятсяв полях существенноменьшей степени,чем вычисленияс суммами Гаусса.Это главнаяпричина, покоторой суммыЯкоби предпочтительнеедля вычислений.При 
выполняетсяклассическоесоотношение 
связывающеесуммы Гауссас суммами Якобии позволяющеепереписатьсравнениетеоремы 3 в терминахсумм Якоби.Так. при
и 
соответствующеесравнение,справедливоедля простых ,отличных от2,3,7, принимаетвид 
,где
и 
- некоторыйкорень кубическийиз 1.В 1984 г. быловнесено существенноеусовершенствованиев алгоритм,позволившееосвободитьсяот требованиянеделимостичисел
на квадратыпростых чисел.В результате,например, выбравчисло 
и взяв равным произведениюпростых чисел с условием, что 
делится на ,получим 
,что позволяетдоказыватьпростоту чисел ,записываемыхсотней десятичныхзнаков. Приэтом вычислениябудут проводитьсяв полях, порождённыхкорнями из 1степеней 16, 9, 5 и7.Персональныйкомпьютер спроцессоромPentium-150.пользуясьреализациейэтого алгоритмана языке UBASIC,доказал простотузаписываемого65 десятичнымизнаками, большегоиз простыхчисел в примереРивеста, Шамираи Адлемана за8 секунд. Сравнениеэтих 8 секунди 17 лет, потребовавшихсядля разложенияна множителипредложенногов примере числа,конечно, впечатляет.
Отметим,что опенкасложности этогоалгоритмапредставляетсобой труднуюзадачу аналитическойтеории чисел.Как уже указывалось,количествоопераций оцениваетсявеличиной
.Однако соответствующиечисла и ,возникающиев процесседоказательства,не могут бытьявно указаныв зависимостиот .Доказано лишьсуществованиечисел и ,для которыхдостигаетсяоценка. Впрочем,есть вероятностныйвариант алгоритма,доказывающийпростоту простогочисла с вероятностьюбольшей 
за 
арифметическихопераций. А впредположениирасширеннойгипотезы Риманаэта опенкасложности можетбыть полученапри эффективноуказанных и .4.ПРАКТИЧЕСКАЯРЕАЛИЗАЦИЯАЛГОРИТМА
Представленныйвыше алгоритмшифрованиябыл реализованс помощьюинтегрированногопакета фирмыBorlandDelphi5.0. Выбор данногоязыка программированияобоснован темчто, он предоставляеттакие возможности,как объектно-ориентированныйподход к программированию,основанныйна формах, интеграцияс программированиемдля Windowsи компонентнаятехнология.Среду визуальногопрограммированияDelphi5 позволяет спомощью компонентногоподхода к созданиюприложений,быстро и качественно"собрать"интерфейспрограммы ибольшую частьвремени использоватьименно на реализациюсоставленногоалгоритма.
Программапостроена потехнологииклиент/сервер,т.е. клиент передаетпо сети данныеиз стандартногопотока ввода(с клавиатуры),предварительнозашифровав,сервер, получаяпоток данных,автоматическиего расшифровывает.
Программныйпродукт состоитиз двух приложений.Первое приложениепредставляетсобой программугенерацииключей. Онавыводит всепростые числазаданногодиапазона, изкоторых потомвыбираютсячисла
и .Там же находятсяоткрытый изакрытый ключи,которые сохраняютсяна диске. Второеприложение,основная программа,производитсоединениемежду двумякомпьютерамии, отправляясообщение,шифрует его.Это приложениеклиент. Приложениесервер получаетсообщение ирасшифровываетего. Так же вовторой программесодержитсянебольшая базаданных абонентов,хранящая в себеимена абонентов,IPадреса и ихоткрытые ключи.4.1.Реализованныеалгоритмы
В программномпродукте былиреализованыосновные алгоритмысхемы RSA.Функция ModDegreeпроизводитвычисление
.Функция Prost находитвсе простыечисла заданногодиапазона.Функция Evklid реализуеталгоритм Евклидаи находит закрытыйключ .Функция HOD производитвычислениенаибольшегообщего делителяи находит открытыйключ .Вышеперечисленныефункции представленыв приложении1. 4.2.Анализ результатов
Результатомработы созданнойпрограммыявляютсязашифрованныеи расшифрованныесообщения.
Для тестированияпрограммыиспользовалсяпример приведенныйв [11]
, 
, 
и 
.Также 
и 
.5.ВЫВОДЫ
Перейдемк обсуждениювыводов последетальногопросмотраспецификиметода, реализованногопрограммногопродукта наоснове построенногоалгоритма, атакже представленногоанализа результатовпо обработанномуматериалу.
5.1 Алгоритм
Использованныйалгоритм RSAимеет рядпреимуществ:
1) алгоритмRSAявляетсяассиметричным,т.е. он основываетсяна распространенииоткрытых ключейв сети. Это позволяетнесколькимпользователямобмениватьсяинформацией,посылаемойпо незащищеннымканалам связи;
2) пользовательсам может менятькак числа
, ,так и открытыйи закрытый ключпо своему усмотрению,только потомон долженраспространитьоткрытый ключв сети. Это позволяетдобиватьсяпользователюнужной емукриптостойкости.При всехэтих преимуществахданный алгоритмимеет существенныйнедостаток– невысокаяскорость работы.Алгоритм RSAработает болеечем в тысячураз медленнеесимметричногоалгоритма DES.
Из всеговышесказанногоможно заключить,что данныйалгоритм шифрования,хотя довольномедленный, ноон ассиметричныйи позволяетдобиватьсянужной криптостойкости,что делает егонезаменимымпри работе внезащищенныхканалах связи.
5.2 Алгоритми программа
Исходяиз проработанныхданных, попостроенномуалгоритму исозданномупрограммномупродукту сделаныследующиевыводы:
1) построенныйалгоритм, асоответственнои созданныйна его базепрограммныйпродукт, полностьюреализуетбазовые механизмысхемы RSAи, таким образомудовлетворяютосновным поставленнымзадачам;
2) данныйпрограммныйпродукт построенпо технологииклиент/сервери предназначенсохранятьконфиденциальностьпередачи информациив сети.
Такимобразом, повыводам о построенномалгоритме исозданномпрограммномпродукте можнозаключить, чтоон подходитдля решенияпроблем шифрованияинформации,связанных спередачейданных по сети.
ЗАКЛЮЧЕНИЕ
В рамках данногодипломногопроектированияперед студентомМалышевым А.А.была поставленазадача: на основеалгоритма RSAдля шифрованияблоков данных,построитьалгоритм иреализоватьпрограммныйпродукт дляшифрованияпотоков данных.
В результатевыполнениядипломногопроектированиябыл составленпринципиальныйалгоритм длярешения поставленнойзадачи. Далееон был детализовани реализованна ЭВМ. В конце,был проведёнанализ полученныхрезультатов,и сделаны необходимыевыводы.
За основу построенияалгоритма былпринят алгоритмRSA для шифрованияблоков данных,изучена соответствующаялитературапо алгоритму,и был построеналгоритм иреализованпрограммныйпродукт в средевизуальногопрограммированияDelphi 5 под ОСтипа Windows дляIBM PC-совместимыхкомпьютеров.
Созданныйпрограммныйпродукт позволяетрешить поставленнуюзадачу и, дополнительно,содержит в себенебольшую базуданных абонентов.Т.е. в результатевыполненияпрограммыисходное сообщениешифруется ипередаетсяпо сети, гдеоно расшифровывается.Также можноуказать о том,что программаимеет интуитивнопонятный интерфейс,что дополнительнопомогает пользователюс наибольшейрезультативностьюиспользоватьвсю ресурснуюбазу.
В заключении,после анализаполученныхрезультатовбыли сделанывыводы, согласнокоторым алгоритмработает иприменим дляпоставленнойзадачи.
СПИСОКИСПОЛЬЗОВАННЫХИСТОЧНИКОВ
1. ЯщенкоВ. В. Основныепонятия криптографии// Математическоепросвещение.Сер. 3. №2. 1998. С. 53-70.
2. ВиноградовИ. М. Основы теориичисел. М.: Наука.1972.
3. КарацубаА. А. Основыаналитическойтеории чисел.М.: Наука. 1983 г.
4. Кнут Д.Искусствопрограммированияна ЭВМ. Т.2: Получисленныеалгоритмы. М.:Мир. 1977.
5.Ахо А.. ХопкрофтДж.. Ульман Дж.Построениеи анализ вычислительныхалгоритмов.М.: Мир. 1979.
6. ВарновскийН. П. Криптографияи теория сложности// Математическоепросвещение.Сер. 3. №2.1998. С.71-86.
7. ВасиленкоО. Н. Современныеспособы проверкипростоты чисел// Кибернетическийсборник, вып.25. 1988. С.162-188.
8. ПрахарК. Распределениепростых чисел.М.: Мир.1967.
9.БоревичЗ.И. ШафаревичИ.Р. Теория чисел.М.: Наука. 1964.
10. КострикинА.И. Введениев алгебру. М.:Наука. 1977.
11. БрассарДж. Современнаякриптология.Мир ПК. №3. 1997.
ПРИЛОЖЕНИЕ1
Листингпрограммы
МодульKey.pas
Function Prost(n:integer):Boolean;
var k:Boolean;
i:integer;
begin
k:=true;
if n2 then
for i:=2 to trunc(sqrt(n))+1 do
if (n/i)=trunc(n/i) then
begin
k:=False;
Break;
end;
Prost:=k;
end;
{________________________________________________________}
Function Evklid(Num1,Num2:integer):integer;
var r,q1,p1:array of integer;
i,n,k:integer;
begin
if Num1>=Num2 then
begin
SetLength(r,10);
r[0]:=Num1;
r[1]:=Num2;
end
else
begin
SetLength(r,10);
r[0]:=Num2;
r[1]:=Num1;
end;
i:=1;
while r[i]0 do
begin
inc(i);
r[i]:=r[i-2] mod r[i-1];
end;
n:=i-2;
SetLength(q1,n+1);
for i:=0 to n do
q1[i]:=r[i] div r[i+1];
SetLength(p1,n+2);
p1[0]:=1;
p1[1]:=q1[0];
k:=length(q1);
if k>1 then
for i:=2 to k do
p1[i]:=q1[i-1]*p1[i-1]+p1[i-2];
Result:=trunc(power(-1,k-1))*p1[k-1] mod Num2;
end;
{________________________________________________________}
Function HOD(Num1,Num2:integer):integer;
var r:array of integer;
i:integer;
begin
if Num1>=Num2 then
begin
SetLength(r,Num2);
r[0]:=Num1;
r[1]:=Num2;
end
else
begin
SetLength(r,Num1);
r[0]:=Num2;
r[1]:=Num1;
end;
i:=1;
While r[i]0 do
begin
inc(i);
r[i]:=r[i-2] mod r[i-1];
end;
Result:=r[i-1];
end;
{________________________________________________________}
Function ModDegree(Num,Degree,n:integer):integer;
var x:array of integer;
i:integer;
begin
SetLength(x,n);
x[1]:=Num mod n;
for i:=2 to Degree do
x[i]:=x[i-1]*Num mod n;
Result:=x[Degree];
end;
ПРИЛОЖЕНИЕ2
Главная формапрограммы
ПРИЛОЖЕНИЕ3
Форма базыданных абонентов
ПРИЛОЖЕНИЕ4
Форма нахожденияпростых чисели генерацииключей
МИНИСТЕРСТВООБРАЗОВАНИЯРОССИЙСКОЙФЕДЕРАЦИИ
АМУРСКИЙГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ
Факультетматематикии информатики
Кафедраматематическогоанализа имоделирования
Специальность010200 – “прикладнаяматематика”
ДОПУСТИТЬК ЗАЩИТЕ
Зав.кафедрой____________________
___________Т.В.Труфанова
«____»_____________2002г.
ДИПЛОМНАЯРАБОТА
натему Применениеалгоритма RSAпри шифрованиипотоков данных
Исполнитель
студентгруппы 752 А. А. Малышев
Руководитель
к.ф.-м.н.,доцент А.Н.Семочкин
Нормоконтроль
к.т.н.,доцент А.Н. Гетман
Рецензент
к.ф.-м.н.,доцент Е.Ф.Алутина
Благовещенск2002
МИНИСТЕРСТВООБРАЗОВАНИЯРОССИЙСКОЙФЕДЕРАЦИИ
АМУРСКИЙГОСУДАРСТВЕННЫЙУНИВЕРСИТЕТ
Факультетматематикии информатики
Кафедраматематическогоанализа имоделирования
Утверждаю:
Зав.кафедрой
_______________________
подпись И.О.Фамилия
«__»_____________200_г.
ЗАДАНИЕ
Кдипломнойработе студентаМалышева АндреяАлександровича
1.Тема дипломнойработы Применениеалгоритма RSAпри шифрованиипотоков данных
(утвержденоприказом от____ №___________)
2. Сроксдачи студентомзаконченнойработы ________________________
3. Исходныеданные к дипломнойработе___________________________
4.Содержаниедипломнойработы (переченьподлежащихразработкевопросов)
Исследоватьсовременныеметоды шифрованияи их приложимостьк шифрованиюпотоков данных.Разработатьсобственнуюбиблиотекуалгоритмовшифрованияи программныйпродукт, демонстрирующийработу этихалгоритмовпри передачеданных в сети.
5.Дата выдачизадания « »____________2002 г.
Руководительдипломнойработы СемочкинАлександрНиколаевичк.ф.-м.н., доценткафедры МАиА.
Заданиепринял к исполнению _____________________________________
РЕФЕРАТ
Дипломнаяработа 48 стр., 11 источников,4 приложения.
АЛГОРИТМRSA,ФУНКЦИЯ ЭЙЛЕРА,ВЗАИМНО ПРОСТЫЕЧИСЛА
В данномдипломномпроекте рассматриваетсязадача анализаалгоритмашифрованиев потоках данныхRSA. Для этогопостроен алгоритми реализованпрограммныйпродукт. Программныйпродукт созданв среде визуальногопрограммированияDelphi 5.0, отлажени протестирован.На основаниианализа полученныхрезультатовсделаны выводы,указаны замечанияи рекомендацииисследователюпо практическомуиспользованиюпрограммы, атакже по дальнейшемуулучшениюалгоритма ипрограммногопродукта вцелом.