{VERSION 17 1 "Windows 7" "17.1" } {USTYLETAB {PSTYLE "Ordered List 1" -1 200 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 } {PSTYLE "Ordered List 2" -1 201 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 36 2 0 2 2 -1 1 }{PSTYLE "Ordered List 3" -1 202 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 72 2 0 2 2 -1 1 }{PSTYLE "Ordered List 4" -1 203 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 108 2 0 2 2 -1 1 }{PSTYLE "Ordered List 5" -1 204 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 144 2 0 2 2 -1 1 }{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 8 8 2 0 2 0 2 2 -1 1 }{PSTYLE "Warning" -1 7 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Annotation Title" -1 205 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 }{PSTYLE "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Ti mes" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 } {PSTYLE "Line Printed Output" -1 6 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 2 2 2 1 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 } {PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 2 2 2 1 3 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Diag nostic" -1 9 1 {CSTYLE "" -1 -1 "Courier New" 1 12 40 120 40 1 2 2 2 2 2 1 2 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Ti mes" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }3 1 0 0 0 0 2 0 2 0 2 2 -1 1 } {PSTYLE "Dash Item" -1 16 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "HyperlinkError " -1 206 1 {CSTYLE "" -1 -1 "Courier New" 1 12 255 0 255 1 2 2 1 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Error" -1 8 1 {CSTYLE "" -1 -1 "Courier New" 1 12 255 0 255 1 2 2 2 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }3 1 0 0 12 12 2 0 2 0 2 2 -1 1 } {PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 4 2 0 2 0 2 2 -1 1 }{PSTYLE "Bullet Item" -1 15 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 4" -1 20 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 1 2 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 1 1 2 2 2 2 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 16 0 0 0 1 2 1 2 2 2 2 1 0 0 1 }1 1 0 0 8 2 2 0 2 0 2 2 -1 1 }{PSTYLE "HyperlinkWarning" -1 207 1 {CSTYLE "" -1 -1 "Courier New" 1 12 0 0 255 1 2 2 1 2 2 1 1 0 0 1 }1 1 0 0 0 0 2 0 2 0 2 2 -1 1 }{PSTYLE "List Item" -1 14 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 0 0 1 }1 1 0 0 3 3 2 0 2 0 2 2 -1 1 } {CSTYLE "Annotation Text" -1 200 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Caption Reference" -1 201 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Maple Input Placeholder" -1 202 "Courier New" 1 12 200 0 200 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "Code" -1 203 "Courier New " 1 12 255 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "2D Inert Output" -1 204 "Times" 1 12 144 144 144 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Hyperlink" -1 17 "Times" 1 12 0 128 128 1 2 2 1 2 2 2 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Maple Input" -1 0 "Courier New" 1 12 120 0 14 1 2 1 2 2 1 2 0 0 0 1 }{CSTYLE "2D Ou tput" -1 20 "Times" 1 12 0 0 255 1 2 2 2 2 2 1 0 0 0 1 }{CSTYLE "2D In put" -1 19 "Times" 1 12 0 0 0 1 2 2 2 2 1 2 0 0 0 1 }{CSTYLE "Header a nd Footer" -1 205 "Times" 1 10 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "T ext" -1 206 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 0 0 0 1 }{CSTYLE "Equatio n Label" -1 207 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "Dic tionary Hyperlink" -1 45 "Times" 1 12 147 0 15 1 2 2 1 2 2 2 0 0 0 1 } {CSTYLE "Atomic Variable" -1 208 "Times" 1 12 175 0 175 1 1 2 2 2 2 2 0 0 0 1 }{CSTYLE "Caption Text" -1 209 "Times" 1 12 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }{CSTYLE "" -1 210 "Times" 1 20 0 0 0 1 2 1 2 2 2 2 0 0 0 1 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 210 26 "Low Exponent attack on R SA" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 49 "We will use command cfrac \+ from numtheory package:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " with(numtheory):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 206 "First, we i ntroduce a couple of commands that we will need. Command cfrac from nu mtheory package computes approximations of a given number by continued fractions. For example, below we approximate number e:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "cfrac(exp(1),7,'f');" }}{PARA 11 "" 1 "" {XPPMATH 20 "-I&CFRACG6\"6#7+\"\"#\"\"\"F'F(F(\"\"%F(F(I$...G6$% *protectedGI(_syslibGF$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 57 "The v ariable f now stores the sequence of approximations:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}{PARA 11 "" 1 "" {XPPMATH 20 "7+\"\" #\"\"$#\"\")F$#\"#6\"\"%#\"#>\"\"(#\"#()\"#K#\"$1\"\"#R#\"$$>\"#rI$... G6$%*protectedGI(_syslibG6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 180 "Recall, that the attack is guaranteed to work if p " 0 "" {MPLTEXT 1 0 35 "p:=nextprime(rand(10^20..10^24)());" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"9@H@BPk\"HlUrd$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "q:=nextprime(rand(p+1000..p+2000)());" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"9tW@BPk\"HlUrd$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n:=p*q;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"QLc!y_$R1vN l==evEl/9$f&\\fz7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 138 "To find e \+ such that d=e^(-1) mod phi(n) < (1/3)n^(1/4) we start from choosing d \+ with this property and then compute e as d^(-1) mod phi(n)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evalf(n^(1/4));" }}{PARA 11 "" 1 "" {XPPMATH 20 "$\"+!)=#4)f\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 41 "So we choose the secret exponent d to be:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "d:=nextprime(rand(10^9..10^10)());" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"+HW44=" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 54 " Just in case we'll check that d and phi(n) are coprime" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "gcd(d,(p-1)*(q-1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 35 "Now \+ we can compute open exponent e:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "e:=d^(-1) mod ((p-1)*(q-1));" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"P4^sbTQ*33USx=e5!e" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 119 "According to the attack, we approximate e/n by continued fractions an d if ed=k*phi(n)+1, we will see k/d as one of them" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "cfrac(e/n,20,'f'):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}{PARA 11 "" 1 "" {XPPMATH 20 "78\"\"!#\"\" \"\"\"##\"\"%\"\"*#\"\"&\"#6#\"#M\"#v#\"#R\"#')#\"#t\"$h\"#\"%*\\\"\"% 1L#\"&M&e\"'&4H\"#\"&L+'\"',C8#\"'m')H\"'*pe'#\"'ltl\"(*z\\9#\"('R8;\" ((HeN#\"(h2F#\"('43]#\"(dT)Q\"($Rm&)#\")v!R+\"\")#)39A#\"*#)RJ9\"\"*&4 ;@D#\"*@5)HN\"*n\"*[y(#\"*.]Hn%\"+i_gI5#\"*CgF?)\"+HW44=#\"/FOOb]'))* \"0;\\vXR/=#I$...G6$%*protectedGI(_syslibG6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 206 77 "Now we run a cycle over all elements of f and for eac h entry P/Q we check if " }{TEXT 206 58 "(e*Q-1)/P is an integer. If s o, we print out the roots of " }{TEXT 206 76 "X^2-(n-C+1)*X+n and obse rve if they are integers. If so, we have factored n." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "for a in f do\n P:=numer(a): Q:=denom(a) :\n if P<>0 then \n" }{MPLTEXT 1 0 47 " C:=(e*Q-1)/P:\n if type (C,integer) then \n" }{MPLTEXT 1 0 16 " print(a);\n" }{MPLTEXT 1 0 37 " print(solve(X^2-(n-C+1)*X+n));\n" }{MPLTEXT 1 0 8 " fi; \n" }{MPLTEXT 1 0 9 " fi;\nod;" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"! " }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "#\"\"\"\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$,&#\"P@@>\"\"\"#\"\"\"*$\"hpd8-aBMtxHH0m;@08h'4)*Qvjb(3 m%p6u*)olS!)3]**p9%eZ$H:@9#F'F&F*,&F$F'F(#!\"\"F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "#\"\"%\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$,& #!OhedA3s%p5THU5D\"3'[hpatNe#\"\"#\"\"\"*$\"fp*yo'))HJ84Z;3>a_v^Xe5&*4 KV#*G1#p&3dAkRa#fc7a\"fDF_[n'#F'F&F*,&F$F'F(#!\"\"F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#M" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#v" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"#R" }}{PARA 11 "" 1 "" {XPPMATH 20 "\" #')" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"#t" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"$h\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"%*\\\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"%1L" }}{PARA 11 "" 1 "" {XPPMATH 20 " \"&M&e" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'&4H\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"&L+'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"',C8" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'m')H" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'*p e'" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"'ltl" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(*z\\9" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"('R8;" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"((HeN" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(h2F#" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"('43]" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"(dT)Q" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"($Rm&)" }} {PARA 11 "" 1 "" {XPPMATH 20 "\")v!R+\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\")#)39A" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"*#)RJ9\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "\"*&4;@D" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"*@5)HN " }}{PARA 11 "" 1 "" {XPPMATH 20 "\"*n\"*[y(" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"*.]Hn%" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"+i_gI5" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"*CgF?)" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"+HW44=" }}{PARA 11 "" 1 "" {XPPMATH 20 "#\"*CgF?)\"+HW44=" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$\"9tW@BPk\"HlUrd$\"9@H@BPk\"HlUrd$" }} {PARA 11 "" 1 "" {XPPMATH 20 "\"/FOOb]'))*" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"0;\\vXR/=#" }}{PARA 11 "" 1 "" {XPPMATH 20 "I$...G6$%*p rotectedGI(_syslibG6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "\"\"\"" }}} {EXCHG {PARA 0 "" 0 "" {TEXT 206 43 "Thus we have recovered our factor s p and q." }}}} {MARK "0 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }