Применение алгоритма RSA для шифрования потоков данных

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

Проблемазащиты информациипутем ее преобразования,ис­ключающегоее прочтениепостороннимлицом, волновалаче­ловеческийум с давнихвремен. Историякриптографии- ровес­ницаистории человеческогоязыка. Болеетого, первоначальнописьменностьсама по себебыла своеобразнойкриптографиче­скойсистемой, таккак в древнихобществах еювладели толькоизбранные.Священные книгидревнего Египта,древней Индиитомупримеры.

Историякриптографииусловно можноразделить на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компьютеров,объединённыхсетью Inter­net.Наконец, отметим,что премия в100$ была переданав FreeSoftwareFoundation.

2.2.Сложностьтеоретико-числовыхалгоритмов

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

Говоряо сложностиалгоритмов,мы будем иметьв ви­ду количествоарифметическихопераций. Припостроенииэффективныхалгоритмови обсужденииверхних оценоксложностиобычно хватаетин­туитивныхпонятий тойобласти математики,которой принадлежиталго­ритм.Формализацияже этих понятийтребуется лишьтогда, когдаречь идёт оботсутствииалгоритма илидоказательственижних опенокслож­ности.

Приведемтеперь примерыдостаточнобыстрых алгоритмовс опен­камиих сложности.Здесь и в дальнейшеммы не будемпридерживатьсяформальногоописания алгоритмов,стараясь впервую очередьобъяснить смыслвыполняемыхдействий.

Следующийалгоритм вычисляетза арифмети­ческихопераций. Приэтом, конечно,предполагается,что натуральныечисла и не превосходятпо величине.

2.2.1.Алгоритмвычисления

1. Представимв двоичнойсистеме счисления,где ,цифры в двоичномпредставлении,равны 0 или 1, .

2. Положими затем для вычислим

.

3)есть искомыйвычет .

Справедливостьэтого алгоритмавытекает изсравнения

,

легкодоказываемогоиндукцией по.

Так каккаждое вычислениена шаге 2 требуетне более трёхумноже­нийпо модулю и этот шагвыполняетсяраз, то сложностьалгоритма можетбыть оцененавеличиной .

Второйалгоритм - этоклассическийалгоритм Евклидавычислениянаибольшегообщего делителяцелых чисел.Мы предполагаемзаданными дванатуральныхчисла и и вычисляемих наибольшийобщий дели­тель.

2.2.2.АлгоритмЕвклида

1. Вычислим- остаток отделения числана ,,.

2. Если ,то есть искомоечисло.

3. Если ,то заменимпару чисел парой и перейдемк
   шагу 1.

Теорема1. При вычислениинаибольшегообщего делителяс помощью алгоритмаЕвклида будетвыполнено неболее операций де­ленияс остатком, гдеесть количествоцифр в десятичнойзаписи меньшегоиз чисел и .

Доказательство.Положим и определим- последовательностьделителей,появляющихсяв процессевыполненияша­га 1 алгоритмаЕвклида. Тогда

.

Пусть также,,,,- последователь­ностьФибоначчи.Индукцией поот до легко доказываетсянеравенство.А так как ,то имеем неравенстваи .

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

2.2.3.Алгоритм решения уравнения

0) Определимматрицу .

1) Вычислим- остаток отделения числана ,,.

2. Если ,то второй столбецматрицы даёт вектор
   решенийуравнения.

3. Если ,то заменимматрицу матрицей .

4. Заменимпару чисел парой и перейдем кшагу 1.

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

Три приведённыхвыше алгоритмаотносятся кразряду такназывае­мыхполиномиальныхалгоритмов.Это названиеносят алгоритмы,слож­ностькоторых оцениваетсясверху степеннымобразом в зависимостиот длины записивходящих чисел.Если наибольшееиз чисел, подаваемыхна вход алгоритма,не превосходит,то сложностьалгоритмовэтого типаоцениваетсявеличиной ,где - некото­раяабсолютнаяпостоянная.Во всех приведённыхвыше примерах.

Полиномиальныеалгоритмы втеории чисел- большая редкость.Да и опенкисложностиалгоритмовчаше всегоопираются накакие-либо недоказанные,но правдоподобныегипотезы, обычноотносящиесяк анали­тическойтеории чисел.

Для некоторыхзадач эффективныеалгоритмывообще не известны.Иногда в такихслучаях всеже можно предложитьпоследовательностьдействий, которая,«если повезет»,быстро приводитк требуемомуре­зультату.Существуеткласс так называемыхвероятностныхалгоритмов,которые даютправильныйрезультат, ноимеют вероятностнуюопен­ку времениработы. Обычноработа этихалгоритмовзависит отодного илинесколькихпараметров.В худшем случаеони работаютдостаточнодолго. Ноудачный выборпараметраопределяетбыстрое завершениера­боты. Такиеалгоритмы, еслимножество«хороших»значений параметроввелико, на практикеработают достаточноэффективно,хотя и не имеютхороших опеноксложности.

Мы будеминогда использоватьслова детерминированныйалгоритм, чтобыотличать алгоритмыв обычном смыслеот вероятностныхалго­ритмов.

Как пример,рассмотримвероятностныйалгоритм, позволяющийэф­фективнонаходить решенияполиномиальныхсравнений попростому мо­дулю.Пусть — простое число,которое предполагаетсябольшим, и - многочлен,степень которогопредполагаетсяограничен­ной.Задача состоитв отысканиирешений сравнения

. (8)

Например,речь может идтио решенииквадратичныхсравнений, еслистепень многочленаравна 2. Другимисловами, мыдолжны отыскатьв поле все элементы,удовлетворяющиеуравнению .

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

Для вычислениямногочленаудобно сначалавычислитьмногочлен ,пользуясьалгоритмом,подобным описанномувыше алгоритмувозведенияв степень (напомним,что число предполагаетсябольшим). А затемс помощью аналогаалгоритмаЕвклида вычислить.Всё это выполняетсяза полиномиальноеколичествоарифметическихопераций.

Такимобразом, обсуждаядалее задачунахождениярешений сравне­ния(8), мы можем предполагать,что в кольцемногочленовспра­ведливоравенство

2.2.4.Алгоритм нахожденияделителеймногочленав коль­це

1)Выберемкаким-либоспособом элемент.

2. Вычислимнаибольшийобщий делитель.

3. Если многочленокажется собственнымделителем ,то многочленраспадётсяна два множителяи с каждым изних незави­симонужно будетпроделать всеоперации,предписываемыенастоящималгоритмомдля многочлена.

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. Выберемслучайнымобразом число,,и проверимдля
   этого числауказанные вышесвойства 1) и2) п.2.

2. Если хотябы одно из нихнарушается,то число составное.

3. Если выполненыоба условия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).

2. для каждойпары выбранныхчисел ,проводятсятесты, подобныесравнению изтеоремы 3. Еслине удовлетворяеткакому-либоиз
   этих тестов- оно составное.В противномслучае

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, отлажени протестирован.На основаниианализа полученныхрезультатовсделаны выводы,указаны замечанияи рекомендацииисследователюпо практическомуиспользованиюпрограммы, атакже по дальнейшемуулучшениюалгоритма ипрограммногопродукта вцелом.