Алгоритмы с открытыми ключами

8.2 Атаки на алгоритм RSA

Для расшифрования необходимо по известным $$N$$, $$e$$ и шифртексту $$y$$ найти такое $$x\in \mathbb{Z}_N^\ast$$, что $$y=x^e (\mod N)$$.

Попытаемся решить сравнение при конкретных $$y$$, затем использовать гомоморфность отображения $$D(x)$$.

Один из возможных способов следующий: пусть имеется набор пар:

с условием, что $$x_i^e = y_i ~(\mod N)$, $1<y<N$$, $$\GCD(y,N)=1$$. Если каким-либо образом удалось представить $$y$$ в виде $$y=y_1^{s_1} y_2^{s_2}\cdots y_k^{s_k} ~(\mod N)$$ с целыми $$s_k$$, то $$x=x_1^{s_1}x_2^{s_2}\cdots x_k^{s_k}$$ будет решением сравнения $$y=x^e ~(\mod N)$$.

Пример 8.3 В наличии имеется открытый ключ $$N = 31459$$, $$e = 5$$ и набор пар соответствующих друг другу исходных и зашифрованных сообщений: $$(23, 18707)$$, $$(755, 26871)$$, $$(631, 6384)$$. Требуется расшифровать шифртекст $$y = 11 638$$.

Представим $$y$$ в виде $$y=18707^{-1}\cdot 26871^3\cdot 6384^{-2}=11 638$$. Отсюда легко вычислить исходное сообщение: $$x=23^{-1}\cdot 755^3 \cdot 631^{-2}=28260$$.

Заметим, что этот подход не менее труден, чем поиск алгоритма решения сравнения $$y=x^e ~(\mod N)$$.

Взлом RSA при неудачном выборе параметров криптосистемы

Само по себе использование RSA не обеспечивает безопасности. Дело еще в деталях реализации. Приведем ряд примеров. Для простоты вычислений будем работать с небольшими числами. Цель - показать особенности, не зависящие от размера.

Пример 8.4 Пусть пользователь выбрал $$N=2047$$, $$e=179$$, $$d=411$$. Так как $$2047 = 23 \cdot 89$$, а числа $$\varphi(23)=22$$ и $$\varphi(89)=88$$ имеют наименьшее общее кратное 88, то любое обратное к 179 по модулю 88, например 59, будет действовать как $$d$$.

Пример 8.5 Число $$N = 536813567$$ является произведением простого числа Мерсенна $$8191$$ и простого числа Ферма $$65537$$. Это очень плохой выбор.

Пример 8.6 Число $$23360947609$$ является очень плохим выбором для $$N$$ из-за того, что два его простых делителя слишком близки к друг другу.

Пусть $$p>q$$, тогда имеем:

Так как $$S$$ мало, то $$t$$ - целое число, лишь немного большее $$\sqrt{N}$$, причем $$t^{2}-N$$ является полным квадратом. Проверяем подряд целые числа $$t>\sqrt{N}$$. В нашем примере это $$t_1 = 152843$$, $$t_2 = 152844$$, $$t_3 = 152845$$, причем $$t_3^2-N=804^2$$. Тогда $$p = 152845 - 804$$. Таким образом, мы с третьей попытки нашли $$p$$ и $$q$$. Количество попыток, необходимых для факторизации $$N$$, можно при известных $$p$$ и $$q$$ вычислить по следующей формуле:

где $$[x]$$ - операция округления $$x$$ до ближайшего целого числа.

Атака методом цепных дробей

См. [1]

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

Теорема 8.1 (Винер) Пусть в системе RSA выполняются неравенства $$p<q<2p$$ и $$d<\dfrac{1}{3}\sqrt[{4}]{n}$$. Тогда по открытому ключу $$(n,e)$$ можно вычислить секретный показатель $$d$$.

При некотором целом $$k$$ выполняется неравенство:

Число дробей $$\dfrac{k}{d}$$, для которых $$d<n$$, удовлетворяющих полученому соотношению, не превосходит $$log n$$, и все они являются подходящими дробями $$\dfrac{P_i}{Q_i}$$ к рациональному чилу $$\dfrac{e}{n}$$. Для некоторого $$i$$ будет выполняться равенство $$\dfrac{P_i}{Q_i}=\dfrac{k}{d}$$. Из равенства $$ed-k\varphi(n)=1$$ следует, что числа $$k$$ и $$d$$ взаимно просты, значит, $$k=P_i$$, $$d=Q_i$$.

Пример 8.7 Пусть $$(n,e)=(4617790059809965777,2693216516134636609)$$ - открытый ключ. Найдём $$d$$.

Раскладываем число $$\dfrac{e}{n}$$ в цепную дробь и находим последовательно подходящие дроби:

Для девятой подходящей дроби получаем, что разность $$e\cdot Q_9 - 1$$ делится нацело на $$P_9$$:

Полагаем $$d=Q_9=5449$$. Секретный ключ найден.

Атака повторным шифрованием

Строим последовательность: $$y_1=y$$, $$y_i=y_{i-1}^e ~(\mod N)$$, $$i>1$$. Итак, $$y_m=y^{(e^m)} ~(\mod N)$$, а так как $$\GCD(e,\varphi(n))=1$$, то существует такое натуральное число $$m$$, что $$e^m=1 ~(\mod \varphi(N))$$. Но тогда $$y^{(e^m-1)}=1 ~(\mod N)$$, отсюда следует, что $$y^{(e^m)} =y ~(\mod N)$$, значит, $$y_{m-1}$$ - решение сравнения $$y=x^e ~(\mod N)$$.

Пример 8.8 Пусть у нас имеется открытый ключ $$N =84517$$, $$e = 397$$ и зашифрованное им сообщение $$y = 8646$$. Найдём открытый текст $$x$$.

Возводя $$y$$ в степень $$e$$, строим последовательность:

Следовательно, $$y_6$$ является решением сравнения $$y=x^e ~(\mod N)$$, а, следовательно, искомым сообщением $$x$$.

Замечание. Анализ метода повторного шифрования хорошо показывает необходимость соблюдения требований на выбор $$p$$ и $$q$$ для обеспечения стойкости. В данном примере $$d = 82 225$$. Неудачный выбор криптосистемы привел к тому, что атака методом повторного шифрования дала результат почти сразу, тогда как нахождение $$d$$ потребовало бы на порядок больших вычислений.

Атака на основе Китайской теоремы об остатках

Как отмечалось ранее, системы шифрования с открытыми ключами работают сравнительно медленно. Для повышения скорости шифрования RSA на практике используют малую экспоненту зашифрования.

Если выбрать число $$e$$ небольшим или таким, чтобы в его двоичной записи было мало единиц, то процедуру шифрования можно значительно ускорить. Например, выбрав $$e = 3$$ (при этом ни $$p - 1$$, ни $$q - 1$$ не должны делиться на 3), мы сможем реализовать шифрование с помощью одного возведения в квадрат по модулю $$N$$ и одного перемножения. Выбрав $$e=2^{16}-1=65537$$ - число, двоичная запись которого содержит только две единицы, мы сможем реализовать шифрование с помощью 16 возведений в квадрат по модулю $$N$$ и одного перемножения. Если экспонента $$e$$ выбирается случайно, то реализация шифрования по алгоритму RSA потребует $$s$$ возведений в квадрат по модулю $$N$$ и в среднем $$s/2$$ умножений по тому же модулю, где $$s$$ - длина двоичной записи числа $$N$$. Вместе с тем, выбор небольшой экспоненты $$e$$ может привести к негативным последствиям. Дело в том, что у нескольких корреспондентов могут оказаться одинаковые экспоненты $$e$$.

Пусть, например, три корреспондента имеют попарно взаимно простые модули $$N_1$$, $$N_2$$, $$N_3$$ и общую экспоненту $$e = 3$$. Если еще один пользователь посылает им некое циркулярное сообщение $$x$$, то криптоаналитик противника может получить в свое распоряжение три шифрованных текста $$y_i=x^3 ~(\mod N_i)$$, $$i=1,2,3$$. Далее, он может найти решение системы сравнений, лежащее в интервале $$(0,N_1\cdot N_2 \cdot N_3)$$ и удовлетворяющее уравнениям:

По китайской теореме об остатках такое решение $$y$$ единственно, а так как $$x^3<N_1\cdot N_2 \cdot N_3$$, то $$y=x^3$$. Значение $$x$$ можно найти, вычислив кубический корень $$x=\sqrt[3]{y}$$. Отметим, 8.1 что выбор малой экспоненты расшифрования $$d$$ также нежелателен в связи с возможностью определения $$d$$ простым перебором. Известно также что если $$d<\sqrt[4]{N}$$, то экспоненту $$d$$ легко найти, используя непрерывные дроби.

Пример 8.9 Три пользователя имеют модули $$N_1=26549$$, $$N_2= 45901$$, $$N_3 = 25351$$. Все пользователи используют экспоненту $$e = 3$$. Всем пользователям было послано некое сообщение $$x$$, причем пользователи получили сообщения $$y_1 = 5366$$, $$y_2 = 814$$, $$y_3 = 4454$$. Найдём $$x$$.

С помощью китайской теоремы об остатках решим систему:

Для этого вычислим $$M_0 = N_1\cdot N_2\cdot N_3= 30893378827799$$. Далее находим

Отсюда $$x=\sqrt[3]{1000000000} = 1000$$ - исходное сообщение, отправленное пользователям.

Бесключевое чтение

Пусть два пользователя выбрали одинаковый модуль $$N$$ и взаимно простые экспоненты $$e_1$$ и $$e_2$$. Если один пользователь посылает им некое циркулярное сообщение $$x$$, то криптоаналитик противника может получить в свое распоряжение два шифрованных текста $$y_1=x^{e_1} ~(mod\; N)$$ и $$y_2=x^{e_2}~(mod\; N)$$. В таком случае криптоаналитик может получить исходное сообщение, найдя с помощью алгоритма Евклида числа $$r$$ и $$s$$ такие, что $$re_1+se_2=1$$. Отсюда получаем:

Пример 8.10 Два пользователя применяют общий модуль $$N = 137759$$, но разные взаимно простые экспоненты $$e_1=191$$ и $$e_2 = 233$$. Пользователи получили шифртексты $$y_1=60197$$ и $$y_2= 63656$$, которые содержат одно и то же сообщение. Найдем исходное сообщение методом бесключевого чтения.

Так как $$e_1$$ и $$e_2$$ взаимно просты, то найдем такие $$r$$ и $$s$$, что $$re_1+se_2=1$$. С помощью расширенного алгоритма Евклида находим $$r = 61$$, $$s = -50$$. Искомое сообщение:

Выводы

Как видно из приведенных выше примеров, выбор параметров криптосистемы является ответственной задачей. Параметры необходимо выбирать в строгом соответствии с требованиями. Существующими в настоящими время методами (и при использовании существующих в настоящее время вычислительных мощностей) атака на алгоритм и/или криптосистему возможна лишь при неудачном выборе параметров. В частности, необходимо обеспечить каждому пользователю уникальные значения $$p$$, $$q$$ и уникальное значение $$e$$, удовлетворяющие требованиям, приведенным выше.

8.3 Примеры атак на алгоритм RSA с большими числами

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

Для работы с большими числами мы будем использовать систему компьютерной алгебры Maxima (см. параграф 1.16.1). Используемые нами функции подробно описаны в руководстве пользователя. Особенно полезен нам раздел "Number Theory".

8.3.1 Пример проведения атаки методом Ферма

Исходные данные:

$$N$$ = 6915244609579137267327382519799379091524149293244816637691826 9398622964367867570234227167749609782487603063343406242777371955314645 2742388332988733993605091994058293499382971742490952474719828474075078 5896707348622744531600003265917743044563775026361237516233569510776114 8109796496185649768169137389070008752782413652613114179194481058554254 4448615819662193369744739530133016244020607483919296703035335756025782 1198618093610413148915963990789275952977743453275495105952399715239534 1404522821690462029654934969262380866920267097617165707930262759302606 756755216795383122881029602333988711966716180750531605801919527461

$$e$$ =7423489;

шифртекст $$C =$$ 465060673245728679820089043475674731352115350813536 29127993992486567556 7156900806763889151763924735496714794491888355277 38596815041010164916640784130 4910760438532601276748143258914433560279 13186272146910522595250621775809097843 8466376070439866602619174245254 91796789390336635629378578035857597525297590776 2618424271931719171731 88933063050921552961787237676274649516864417659967226409 6655987478676 94982197189302733688441148495741687268763633927764999172932586878 6575 5502667348346941062611020674418896448890646803651538990666737332006313 6883 39309056851281655672233726633413389794443264266190435226307846633 6457114523067

e:7423489$
     

srn:isqrt(N)$

is(srn^2=N);
     

(%o5)    false
     

(%i6) w1 : (srn+1)^2 - N$
(%i7) is(isqrt(w1)^2=w1);
(%o7)      false
(%i8) w2 : (srn+2)^2 - N$
(%i9) is(isqrt(w2)^2=w2);
(%o9)      false
(%i10) w3 : (srn+3)^2 - N$
(%i11) is(isqrt(w3)^2=w3);
(%o11)      false
(%i12) w4 : (srn+4)^2 - N$
(%i13) is(isqrt(w4)^2=w4);
(%o13)      true
     

(%i14) p:srn+4-isqrt(w4);
(%o14) 262968526816026736232636051189459874382446519148
       963617629027255104769945719755984982102707120117
       706525064015257076350250162229292374187259939548
       939791858838514297011479606873615542587565445952
       774014851457711890959298629102287714458214768091
       456036071496351940116236181014737608169537866387
       475270200449701600539
(%i15) q:srn+4+isqrt(w4);
(%015) 262968526816026736232636051189459874382446519148
       963617629027255104769945719755984982102707120117
       706525064015257076350250162229292374187259939548
       939791858918434644001891354485948817612831393943
       831874217795402559116173347849761999726607005334
       107474067053693923414485042904885419841498167834
       826934556836972951999
     

(%i16) is(N=p*q);
(%o16)     true
     

(%i17) n:(p-1)*(q-1);
(%o17) 691524460957913726732738251979937909152414929324
       481663769182693986229643678675702342271677496097
       824876030633434062427773719553146452742388332988
       733993605091994058293499382971742490952474719828
       474075078589670734862274453160000326591774304456
       377502636123751623356951077611481097964961856497
       681691373890700087522564765989810607067292089561
       753346960966889279214097392158985030920845106212
       364219654648892933401895280839556667834036311647
       010551595182396506795549490371941105829837814339
       818401626212936221330490459000092664168447951206
       651159937454409858770432466166667495195921598056
       82710960700930681958448326848515244974924
     

(%i18) d:inv_mod(e,n);
(%o16) 159473778881412178951363380047548370299185595369
       293301556900463792194735837486992335590486755090
       118784764988909430054104623893214000053083933271
       592133656057039185769018422628707296349955436619
       729220378775558752251642918675436409902022493957
       029259927562211781124457194260217400235337672814
       214944366331695859094533195686344563818416832875
       322618995339315686613690403531225496361587681392
       769069101695698479902470067182274377952892405921
       601214570482225781950523126294764189240377630662
       614360117188441324480392776069704371618231484929
       589094831167041492978941304862403054017212391664
       53872109949533807664476342715222105274029
     

(%i19) P:power_mod(C,d,N);
(%o19)     20231718
     

8.3.2 Пример выполнения атаки "бесключевое чтение"

Исходные~данные:

$$N=$$ 2519590847565789349402718324004839857142928212620403202777713 7836043662020707595556264018525880784406918290641249515082189298559149 1761845028084891200728449926873928072877767359714183472702618963750149 7182469116507761337985909570009733045974880842840179742910064245869181 7195118746121515172654632282216869987549182422433637259085141865462043 5767984233871847744479207399342365848238242811981638150106748104516603 7730605620161967625613384414360383390441495263443219011465754445417842 4020924616515723350778707749817125772467962926386356373289912154831438 167899885040445364023527381951378636564391212010397122822120720357;

$$e_{1} = 1011163$$; $$e_{2} = 1110521$$;

$$C_{1} =$$ 1475325512646127242922491234336573821326644830122724857802651 82834500418 6248451852916071172167393901484963211012186813420799457345 60638901218485778028 8088167762693301487173478582573846232471858233011 05429274234279863037579651294 1305440048424158412512493520129752032822 49047843226000864924203675006878533759 4689790689579026501643817929120 04105626763672704672827848013136399268699306662 7592945775958095422456 50919791860840020082746913903995338683355323748300077852 4222905192914 54785850041002811165491890932478197036280409606904111958813351896 3410 8240519966700126623731566589570806848893829480888979012581343525399802 490

$$C_{2} =$$ 1168960834050268961897324310220295239101276316289170220279034 24838605267 3641103792818084219415738429514299664733141986982322386646 78264765952517495919 5383277543494845172200901017398976983581548883677 72471406710688871011254842119 0717106834141930230321678867355741169178 64117261510578555710832001442414172654 4343094430367130161092842091138 95716177545680184852854836102034397952992257055 3742268402669724738982 06540435293792709985777111719850811784302488645684794421 4372490969359 76159712998481145184343878513509137590163314701862659532716478010 6260 3880245750910942198158465793549050643147723479955672632110054161976725 720

(%i6) [u1,u2,v]:igcdex(e1,e2);
(%o6)        [- 185750, 169131, 1]
     

(%i7) m:mod(power_mod(c1,u1,N) * power_mod(c2,u2,N),N);
(%o7) 17109930102028242618171032184099141023232413249933
      18272110992310172310331523109923101326101410991299
      14121527281899283727413399142421211926241299273410
     

Теперь, используя таблицу 6.1 (см. лекцию 6), нетрудно прочитать зашифрованный текст:

ЗА ФАКТОРИЗАЦИЮ ДАННОГО ЧИСЛА НАЗНАЧЕНА НАГРАДА В ДВЕСТИ ТЫСЯЧ ДОЛЛАРОВ США
    

Действительно, за разложение на множители данного модуля положена награда в 200~000 долларов США. Маловероятно, что такая награда была бы назначена, если бы операция факторизации чисел такого размера была бы легкой задачей. Приведенный пример показывает, что криптосистема хоть и была построена на основе числа, надежность которого оценивается столь большой суммой, из-за неверной реализации и нарушения правил безопасного использования алгоритма RSA была проведена успешная атака на такую систему.

8.3.3 Пример выполнения атаки на основе китайской теоремы об остатках

Исходные~данные:

$$N_{1}=$$ 2620595590763345144693186700359738170637959124766023390552357 7708743486405826754889134908712878889866426949841420594546127374968746 3704691027597982381045792187752115484056255124356418017823267456319147 0945512881726415778968582505568195308039434983677266976473866499763291 3738820183706821310507433203861937132913052549942960788848335390037394 6608954216027382001077261982166703560129855861608144340546877016429583 9526450906080526730620279528287119758899389543943591998158763938922196 8046758300050695830713985416717597991930870022544853965458777962931909 648137289765408375166634394924214994296219013143450580985614906283;

$$N_{2 } =$$ 1404373956322280634703446579661705045380233929445038795196910 8939191622721351334042117943027988219739179215127857273262112408720857 5085635334263838298981285414802497708344255137307727529188557129111432 3963768294617167632028510681829911856058478660674376664320832126316894 7606402829166495400694730956929734685472783298926965979178579784105662 8153673135054858125822469223977739610372727151870093086752152869771307 3467493421736819899669678212641557159981424135655309012610054286808387 9520929487076060467246719139718422376341840235179419394933429027866125 906378222980586843220420100138771858151139634024553669934223886607;

$$N_{3} =$$ 1678762549783158397789297902611957781442911408001435228447125 0202063154360775415905721304251931956720446037943647416174134426911566 5212990059682834427697301545254518302708049934908529962522695547077196 3230698471528227970703734830356915746959604252425636041283401479887740 4322176725761721902946480880822193710599559142350970463792284136048849 7544583768616918174829041738653440422210516040921622855920557488080866 4309140695930461054347617641431967212377776787337055888304116258297846 9227591560752572050022468537356199792558856097689011471958919584692498 500245987683611873312532240213872073959474934338996846004302775537;

$$C_1=$$ 4927139668939115071182968571701562304473718670620554307010688 1062090413635818301115427131412979009259007051009291844710074543775650 6516091527776544977721235554003704444593860610457655753309542143091955 7022261909268967057374961078768152217628589481286924844350506066728881 1473812492507877737379593844465799176180271907072851233493907805067518 8437332715271665418501912559134109018864658897093701890552483116702122 6061148157077899368221090313561236504179559243208369732033772455827306 9885989713330049648986010254199574027123751067293726506915040515035321 29413622932103918478494329377614278246377310198475360664888159698

$$C_2=$$ 3968904170996511074822512049317096671468123928927710698588786 2347631886514250093559580298720231340125645657836036173135232353725327 1463638334669264317836171769199659586183542349898954031121711885587682 9157809932216110967296980031363470360774569191729660576200413662944516 2239552010112356886221078835918681512698544646875041376476380679149594 6228326687802420878384865328494980645673174579578595475235815167063272 6383360324448016877640031260359897273404846113595628745775834042432714 2510945980040123373707520807207125269432787473039210714621060676962495 55526071081634210584640898292343334109384890322861662213339826806

$$C_3=$$ 2693434464101963658612411044117300168679280228386801221153426 9534648413073139833416490884467353782556651124872003929791054528059521 9750178127743617105872428304027181612949559624296295303659876228036366 1172080005585577843506210407098282557890991077271720540702078785134336 4204874516864307636270232905646677124930139153281613748156352379189398 0516732942593222620332350649515771205783855908682127130916311303600896 2726424558876252115570834611302696707152581624589109290455282184973051 7701394206986426270816677531308584524442338494896621843059785765006275 39756315409235915749943340705460409673942434752665551704951603699

$$e=3$$. Найдём сообщение $$m$$.

(%i8) mcube:chinese([c1,c2,c3],[N1,N2,N3]);
(%o8) 1439619746877070775526192128945758968992165680996
      3966572720001979003084347216085169846710176736442
      2607102784602056703967564355254187236240029273958
      5244623799154989886682303658655987332618285682692
      1673617098179274483891388669524107519774675750988
      5071342316383704181434566679343998766513563861662
      3709617247882929434704037023359692069389958441799
      9598227129708607068497886977208029397728335933695
      8553982958213317414845600724816716404544112021449
      4656103946055056386082865741853419774396410771345
      3805185312405889293788831589145513935021181672031
      6464546892480620465275275072448707709191544241239
      3719042339415429661220875253048244629952
     

(%i9) m:inrt(mcube,3);
(%o9) 1129143828159925261514152138232499122318221028152
      1382337992526189912371124261599251026102215282624
      1299341830262427182728152237991099282499121034159
      9272424113515231815991415341830262940289918992526
      24331828104028
(%i10) m^3-mcube;
(%o10) 0
     

Вновь декодируем результат по таблице 6.1 (см. лекцию 6):

БУДЬТЕ ПРЕДЕЛЬНО ВНИМАТЕЛЬНЫ ПРИ ВЫБОРЕ ПАРАМЕТРОВ ШИФРОСИСТЕМЫ А ТО ВАШЕ СООБЩЕНИЕ ДЕШИФРУЮТ И ПРОЧИТАЮТ
    

8.4 Рюкзачный шифр

См. [2]

Схема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые их этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению? Более формально: дан набор значений $$M_1, M_2, \ldots, M_n$$ и сумма $$S$$. Нужно вычислить значения $$b_i$$ такие, что $$S=b_1 M_1 + b_2 M_2 +\ldots+ b_n M_n$$, где $${b}_{i}$$ может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль - что не кладут.

Например, массы предметов могут иметь значения 1, 5, 6, 11, 14 и 20. Вы можете упаковать рюкзак так, чтобы его масса стала равна 22, использовав массы 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его масса была равна 24. В общем случае время, необходимое для решения этой проблемы, с ростом количества предметов в куче растет экспоненциально.

В основе алгоритма рюкзака Меркла-Хеллмана лежит идея шифровать сообщение как решение набора проблем рюкзака. Предметы из кучи выбираются с помощью блока открытого текста, по длине равного количеству предметов в куче (биты открытого текста соответствуют значениям $$b_i$$), а шифртекст является полученной суммой. Пример шифртекста, зашифрованного с помощью рюкзака в таблице 8.2.

На самом деле существуют две различные проблемы рюкзака, одна решается за линейные время, а другая, как считается,нет. Легкую проблему можно превратить в трудную. Открытый ключ предоставляет собой трудную проблему, которую легко использовать для шифрования, но невозможно для расшифрования сообщений. Закрытый ключ является легкой проблемой, давая простой способ расшифровать сообщения. Тому, кто не знает закрытый ключ, придется попытаться решить трудную проблему рюкзака.

8.4.1 Сверхвозрастающие рюкзаки

Если перечень масс представляет собой сверхвозрастающую последовательность, то полученную проблему рюкзака легко решить. Сверхвозрастающая последовательность - это последовательность, в которой каждой член больше суммы всех предыдущих членов. Например, последовательность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9, 15,25} - нет.

Решение сверхвозрастающего рюкзака найти легко. Возьмите полный вес и сравните его с самым большим числом последовательности. Если полный вес меньше, чем это число, то его не кладут в рюкзак. Если полный вес больше или равен этому числу, то оно кладется в рюкзак. Уменьшим массу рюкзака на это значение и перейдем к следующему по величине числу последовательности. Будем повторять, пока процесс не закончится. Если полный вес уменьшится до нуля, то решение найдено. В противном случае нет.

Например, пусть полный вес рюкзака - 70, а последовательность весов {2,3,6, 13,27,52}. Самый большой вес, 52, меньше 70, поэтому кладем 52 в рюкзак. Вычитая 52 из 70, получаем 18. Следующий вес - 27, больше 18, поэтому 27 в рюкзак не кладется. Вес 13, меньше 18, поэтому кладем 13 в рюкзак. Вычитая 13 из 18, получаем 5. Следующий вес - 6, больше 5, поэтому 6 не кладется в рюкзак. Продолжение этого процесса покажет, что и 2, и 3 кладутся в рюкзак, и полный вес уменьшается до 0, что сообщает о найденном решении. Если бы это был блок шифрования методом рюкзака Меркла-Хеллмана, открытый текст, полученный из значения шифртекста 70, был бы равен 110101.

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

Алгоритм Меркла-Хеллмана основан на этом свойстве. Закрытый ключ является последовательностью весов проблемы сверхвозрастающего рюкзака. Открытый ключ - это последовательность весов проблемы нормального рюкзака с тем же решением. Меркл и Хеллман, используя модульную арифметику, разработали способ преобразования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака.

8.4.2 Создание открытого ключа из закрытого

Рассмотрим работу алгоритма. Чтобы получить нормальную последовательность рюкзака, возьмем сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52}, и умножим по модулю $$m$$ все значения на число $$n$$. Значение модуля должно быть больше суммы всех чисел последовательности, например, 105. Множитель должен быть взаимно простым числом с модулем, например, 31. Нормальной последовательностью рюкзака будет

Итого - {62,93,81,88,102,37}.

Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовательность рюкзака - открытым.

8.4.3 Шифрование

Для шифрования сообщение сначала разбивается на блоки, равные по длине числу элементов последовательности рюкзака. Затем, считая, что единица указывает на присутствие члена последовательности, а ноль - на его отсутствие, вычисляем полные веса рюкзаков - по одному для каждого блока сообщения.

Например, если сообщение в бинарном виде выглядит как 011000110101101110, шифрование, использующее предыдущую последовательность рюкзака, будет происходить следующим образом:

Шифртекстом будет последовательность 174,280,333.

8.3.4 Расшифрование

Законный получатель данного сообщения знает закрытый ключ: оригинальную сверхвозрастающую последовательность, а также значения $$n$$ и $$m$$, использованные для превращения ее в нормальную последовательность рюкзака. Для расшифрирования сообщения получатель должен сначала определить обратный к $$n$$ по модулю $$m$$. Каждое значение щифротекста умножается на $$n^{-1}~(\mod m)$$, а затем разделяется с помощью закрытого ключа, чтобы получить значения открытого текста.

Для расшифрования используется выбранная ранее сверхвозрастающая последовательность {2, 3, 6, 13, 27, 52} с $$m=105$$, $$n = 31$$. Шифртекстом служит 174,280,333. В этом случае $$n^{-1}=61 ~(\mod m)$$, поэтому значения шифртекста должны быть умножены на 61 по модулю 105.

Расшифрованным открытым текстом является 011000 110101 101110.

8.4.5 Практические реализации

Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовательность не является сверхвозрастающей. Реальные рюкзаки должны содержать не менее 250 элементов. Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами, а длина модуля должна быть от 100 до 200 битов. Для получения этих значений практические реализации используют генераторы псевдослучайной последовательности.

8.5 Алгоритм Блюма-Блюма-Шуба

Одним из наиболее стойких к криптографическим атакам является алгоритм Блюма-Блюма-Шуба (BBS). Главное его достоинство состоит в том, что строго доказано, что не существует алгоритма с полиномиальной оценкой времени его выполнения, который по любым $$k$$ битам выходной последовательности может предсказать ее $$(k+1)$$-й бит с вероятностью, существенно большей, чем 0,5.

Пусть $$p$$ и $$q$$ - два больших простых числа примерно одинакового размера, причем

Тогда число $$n=\mathit{pq}$$ называется целым числом Блюма. Пусть $$\mathbb{Z}_n^\ast$$ - мультипликативная группа кольца вычетов по модулю $$n$$, $$Q{R}_{n}$$ - подгруппа её квадратов. Имеем:

Каждый квадрат из $$Q{R}_{n}$$ имеет ровно четыре квадратных корня в $$\mathbb{Z}_n^\ast$$, и лишь один из них, называемый примитивным, лежит в $$Q{R}_{n}$$.

Пример 8.11 Если $$p=19,q=23$$, то $$n=437$$. Тогда $$133=19{\cdot}7{\notin}\mathbb{Z}_{437}^\ast$$, $$135{\in}\mathbb{Z}_{437}^\ast$$, $$139{\in}\mathbb{Z}_{437}^\ast$$, кроме того, учитывая, что корня из 135 по модулю 437 не существует, а $${24}^{2}=139~(\mod 437)$$, имеем:

Квадратными корнями из 139 по модулю 437 являются числа 24, 185, 252 и 413, причем 24 является примитивным, поскольку $${47}^{2}=24~(\mod 437)$$.

Задача определения примитивных квадратных корней по модулю числа $$n$$ вычислительно эквивалентна задаче разложения этого числа на множители. Таким образом, функция

эффективно вычисляется, а произвести обратное преобразование может только тот, кто знает секрет - разложение $$f(x)$$ на множители. Таким образом, $$f(x)$$ - односторонняя функция с секретом.

Опишем теперь алгоритм генерации случайной последовательности чисел.

Пусть $$n$$ - целое число Блюма.

Важным достоинством этого генератора является то, что при знании разложения $$n$$ на простые множители он допускает прямое определение отдельных битов, которые в нём вырабатываются. Имеем:

причем $${x}^{(p-1)(q-1)}=1~(\mod n)$$, поэтому

то есть с помощью двух операций модульного возведения в степень, которые эффективно вычисляются, любое число $${x}_{i}$$ может быть найдено лишь исходя из начального вектора $${x}_{0}$$ и индекса $$i$$.

Термин вероятностное шифрование был введён Ш. Гольдвассер и С. Микали, и ими же была предложена первая схема такого шифрования, основанная на использовании BBS-генератора в качестве источника ключевой последовательности. Данная схема не обеспечивает секретности по отношению к атаке на основе выбранного шифртекста.

Пусть исходное сообщение $$t$$ - $m$-разрядная битовая последовательность, $${x}_{0}$$ - случайный квадратичный вычет по модулю $$n$$. Функция шифрования по схеме Гольдвассер-Микали имеет вид:

при этом $${x}_{m}$$ включается в шифртекст для того, чтобы законный получатель мог его расшифровать. При этом для расшифровки вычисляется $${x}_{0}$$ по следующему алгоритму:

где $$a$$ и $$b$$ находятся расширенным алгоритмом Евклида: $$ap+bq=1$$.

Пример 8.12 Каждой букве русского алфавита (отождествим Е и Ё) поставим в соответствие её порядковый номер в двоичной записи:

Зашифруем слово "шифр" по алгоритму вероятностного шифрования.

Используя приведенную схему кодирования, получаем:

Выберем простые числа: $$p=100699,q=100943$$. Тогда $$n=10164859157$$. Возьмём случайный квадратичный вычет $${x}_{0}=2081895771$$ по модулю $$n$$. Последовательно возводя его в квадрат, получаем:

Получаем шифртекст: $$c=(9863050867,01110111101111000011)$$.

Пример 8.13 Шифртекст $$c$$ получен из слова в алфавите А, Б, ..., Я по схеме вероятностного шифрования с использоваем открытого ключа $$n=pq$$. Найти открытый текст. $$p=101987$$, $$q=101267$$, $$c = (9775365428, 11010000001111001000)$$.

Имеем $$m=19$$, $$n=pq = 101987 \cdot 101267 = 10327917529$$.

Расшифровку проведем по алгоритму (8.1):

1) Вычисляем $$\alpha$$ и $$\beta$$:

2) Находим $$u$$ и $$v$$:

3) С помощью алгоритма Евклидва найдём целые числа $$a$$ и $$b$$ такие, что $$ap+bq=1$$, т.е. $$a=p^{-1}(\mod q)$$, $$b=q^{-1}(\mod p)$$. Получаем: $$a=5204$$, $$b=-5241$$.

4) Находим $$x_0$$:

Теперь вычисляем $$x_1, \ldots, x_{19}$$:

Прибавляя поразрядно последовательность $$x_0 ~(\mod 2)$$, $$x_1 ~(\mod 2)$$, $$\ldots$$, $$x_{19} ~(\mod 2)$$ к шифрограмме, получаем код исходного сообщения:

8.6 Шифрование на основе группы точек эллиптической кривой

Опишем аналоги некоторых широко распространенных систем с открытым ключом, основанные на задаче дискретного логарифмирования на эллиптической кривой, определенной над конечным полем $${F}_{q}$$.

8.6.1 Ключевой обмен

Предположим, что абоненты А и Б хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего, они открыто выбирают какое-либо конечное поле $${F}_{q}$$ ($$q=p^r$$) и какую-либо эллиптическую кривую $$E$$ над ним. Их ключ строится по случайной точке $$P$$ на этой эллиптической кривой. Если у них есть случайная точка $$P$$, то, например, ее $$x$$-координата дает случайный элемент $${F}_{q}$$, который можно затем преобразовать в $$r$$-разрядное целое число в $$p$$-ричной системе счисления, и это число может служить ключом в их классической криптосистеме. Они должны выбрать точку $$P$$ так, чтобы все их сообщения друг другу были открытыми и все же никто, кроме них двоих, ничего бы не знал о $$P$$.

Абоненты (пользователи) А и Б первым делом открыто выбирают точку $$G\in E$$ в качестве "основания". Чтобы образовать ключ, абонент А вначале случайным образом выбирает целое число $$a$$, это число он держит в секрете. Он вычисляет $$aG\in E$$ и передает эту точку открыто. Абонент Б делает то же самое: он выбирает случайно $$b$$ и открыто передает $$bG\in E$$. Тогда используемый ими секретный ключ - это $$P=abG\in E$$. Оба пользователя могут вычислить этот ключ. Например, абонент А знает $$bG$$ (точка была передана открыто) и свое собственное секретное a. Однако любая третья сторона знает лишь $$aG$$ и $$bG$$. Кроме решения задачи дискретного логарифмирования - нахождения $$a$$ по $$G$$ и $$aG$$ (или нахождения $$b$$ по $$G$$ и $$bG$$) - по-видимому, нет способа найти $$abG$$, зная лишь $$aG$$ и $$bG$$.

Пример 8.14 Возьмём эллиптическую кривую $$E_p(0,-4)$$, где $$p=211$$, и точку $$G=(2,2)$$. Произведём обмен ключами.

Личным ключом пользователя А является $$a = 121$$, поэтому его открытым ключом будет $$aG =121\cdot (2, 2) = (115, 48)$$. Личным ключом пользователя Б является $$b = 203$$, поэтому его открытым ключом будет $$bG=203\cdot (2, 2) = (130, 203)$$. Общим секретным ключом является

Общий секретный ключ представляет собой пару чисел. Если этот ключ предполагается использовать в качестве сеансового ключа для традиционного шифрования, то из этой пары чисел необходимо генерировать одно подходящее значение. Можно, например, использовать просто координату $$x$$ или некоторую простую функцию от $$x$$.

Криптосистема с открытым ключом для передачи сообщений

Как и в описанной выше системе ключевого обмена, мы исходим из несекретных данных:

Каждый из пользователей выбирает случайное целое число: $$a_\text{А}$$ - у пользователя А, и $$a_\text{Б}$$ - у пользователя Б, которое пользователь держит в секрете. Затем пользователи А и Б вычисляют точки, соответственно, $$a_\text{А} G$$ и $$a_\text{Б} G$$.

Чтобы послать пользователю Б сообщение $$P_m$$, пользователь А выбирает случайно целое число $$k$$ и посылает пару точек $$\{kG, P_m+k a_{\text{Б}} G$$ (где $$a_{\text{Б}} G$$ - открытый ключ пользователя Б). Чтобы прочитать сообщение, пользователь Б умножает первую точку из полученной пары на свое секретное число $$a_\text{Б}$$ и вычитает результат умножения из второй точки:

Таким образом, пользователь А посылает замаскированное сообщение $$P_m$$ вместе с "подсказкой" $$kG$$, при помощи которой можно снять "маску" $$ka_\text{Б} G$$, если знать секретное число $$a_\text{Б}$$. Злоумышленник, который умеет решать задачу дискретного логарифмирования на $$E$$, может, конечно, найти $$a_\text{Б}$$, зная $$a_\text{Б} G$$ и $$G$$.

Пример 8.15 Рассмотрим кривую $$E_p(-1,188)$$ с $$p = 751$$ (что соответствует кривой $$y^2 = x^3-x+188$$) и точкку $$G=(0, 376)$$. Предположим, что пользователь А собирается отправить пользователю Б сообщение, которое кодируется эллиптической точкой $$P_m=(562,201)$$, и что пользователь А выбирает случайное число $$k= 386$$. Открытым ключом пользователя Б является $$P_{\text{Б}} = (201,5)$$.

Мы имеем

Таким образом, пользователь А должен послать шифрованный текст: {(676, 558), (385, 328)}.

8.6.2 Пример кодирования и декодирования текста

См. [3]

Перед шифрованием необходимо выбрать способ кодирования текста. Для этого найдем точки на кривой и некоторым из них поставим в соответствие символы.

Выберем кривую $$E_{751}(-1,1)$$, т. е. $$y^2=x^3-x+1 ~(\mod 751)$$. Таблица 8.3 задаёт соответствие символов и некоторых точек кривой.

Заметим, что мощность множества точек на этой кривой $$N= 727$$, поэтому при необходимости можно точками закодировать и некоторые специальные знаки (например, знак интеграла и т. п.), а также целые слова.

Приведем примеры решения контрольных заданий, представленных ниже.

Пример 8.16 (Шифрование) Пусть выбрана генерирующая точка $$G = (0, 1)$$. Предположим, пользователь $$A$$ решил отправить пользователю $$B$$ сообщение: строчную латинскую букву "A". В нашем алфавите эта буква кодируется точкой $$P_m = (66, 522)$$. Пусть пользователь $$A$$ выбрал случайное значение $$k = 3$$, а открытым ключом $$B$$ является точка $$P_B = (406, 397)$$, при этом секретным ключом $$B$$ является число $$n_b=45$$.

Шифрованный текст имеет вид $$C_m = \{kG, P_m+ k P_B\}$$.

Находим $$kG = 3\cdot (0,1) = (56, 419)$$.

Вычисляем $$P_m+kP_b = (66, 552) + 3\cdot (406, 397) = (301, 734)$$.

В результате: $$C_m= \{(56, 419), (301, 734)\}$$.

Пользователь $$B$$ для расшифрования сообщения должен провести следующие вычисления:

После этого пользователь B по алфавиту определяет открытый буквенный текст: точке (66, 552) соответствует строчная латинская буква A.

Пример 8.17 Кривая: $${E}_{751}(-1,1)$$

Генерирующая точка: $$G=\left(0,1\right)$$

Открытый текст: "терновник"

Открытый ключ: $$(188,93)$$

Значения случайных чисел $$k$$ для букв открытого текста: $$8, 14, 17, 17, 2, 10, 8, 2, 2$$.

Установим соответствие точек кривой буквам:

Расчёт:

Установим соответствие букв и точек шифрованного текста:

Шифртекст: {(346, 242), (594, 414)}; {(596, 433), (34, 677)}; {(440, 539), (546, 670)}; {(440, 539), (694, 581)}; {(188, 93), (515, 684)}; {(377, 456), (517, 573)}; {(346, 242), (288, 639)}; {(188, 93), (209, 82)}; {(188, 93), (205, 379)}.

Пример 8.18 (Расшифрование) Входные данные.

Кривая: $${E}_{751}(-1,1)$$

Генерирующая точка: $$G = (-1,1)$$

Шифртекст: {(377, 456), (367, 360)}, {(425, 663), (715, 398)}; {(188, 93), (279, 353)}, {(179, 275), (128,79)}; {(568, 355), (515, 67)}, {(568, 355), (482, 230)}; {(377, 456), (206, 645)}, {(188, 93), (300, 455)}; {(489, 468), (362, 446)}, {(16, 416), (69, 510)}; {(425, 663), (218,601)}.

Секретный ключ: $${n}_{B} = 44$$.

Расчёт:

Открытый текст - "заостренный".

Список литературы