14 12
發新話題
打印

用Maxima學密碼學-Lattice Reduction應用2-找出同餘方程式較小的解

1-2.刻板訊息(Stereotyped Messages)
當大部分訊息是固定的或刻板的,假設明文\(m\)包含兩個部分。
(1)已知部分\(B=2^kb\),例如"October 19, 1995.The secret key for the day is"的ASCII值。
(2)未知部分\(x\),例如"Squeamish Ossifrage",\(x\)小於\(\displaystyle N^{\frac{1}{3}}\)。

假設RSA加密方案採用公鑰\(e=3\),密文\(C=M^3=(B+x)^3\pmod{N}\),若已知\(B,C,N\),產生多項式\(p(x)=(B+x)^3-C\),找出\(x_0\)滿足\(p(x_0)=(B+x_0)^3-C \equiv 0\pmod{N}\),\(\displaystyle |\;x_0|\;<N^{\frac{1}{3}}\)

參考資料:
Coppersmith, D. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. J. Cryptology 10, 233–260 (1997).
https://link.springer.com/article/10.1007/s001459900030
https://www.di.ens.fr/~fouque/ens-rennes/coppersmith.pdf

顯示數字的全部位數會造成版面凌亂,將太長的數字縮短顯示
功能表選取,編輯/設定/Worksheet/Maximum displayed number of digits調整為60



請下載LLL.zip,解壓縮後將LLL.mac放到C:\maxima-5.45.1\share\maxima\5.45.1\share目錄下
要先載入LLL.mac才能使用Coppersmith_Howgrave指令

(%i1) load("LLL.mac");
(%o1) C:/maxima-5.45.1/share/maxima/5.45.1/share/LLL.mac

明文訊息
(%i2) m:"October 19,1995.The secret key for the day is";
(m) \(October 19,1995.The secret key for the day is\)

明文訊息轉成list
(%i3) mlist:charlist(m);
(mlist) \([O,c,t,o,b,e,r, ,1,9,,,1,9,9,5,.,T,h,e, ,s,e,c,r,e,t, ,k,e,y, ,f,o,r, ,t,h,e, ,d,a,y, ,i,s]\)

明文轉成數字B
(%i4) B:0;
(B) \(0\)

將明文訊息按照ASCII轉換成數字
(%i6)
for i:1 thru length(mlist) do
  (B:B*1000+cint(mlist[ i ])
  )$
B;

(%o6) \(79099116111098101114[94 digits]32100097121032105115\)

密碼x長度19(通常要猜測很多次,為了簡化過程設為已知)
(%i7) length:19;
(length) \(19\)

最後19位000為密碼x
(%i8) B:B*1000^length;
(B) \(79099116111098101114[151 digits]00000000000000000000\)

公鑰e
(%i9) e:3;
(e) \(3\)

使用RSA-230作為此次的公鑰N,因為密碼x小於上界X
https://en.wikipedia.org/wiki/RSA_numbers#RSA-230

(%i10)
N:17969491597941066732916128449573246156367561808012600070888918835531726460341490933493372247868650755230855864199929221814436684722874052065257937495694348389263171152522525654410980819170611742509702440718010364831638288518852689;
(N) \(17969491597941066732[190 digits]64831638288518852689\)

密文C
(%i11)
C:3601065602437181695470302568875441014033597674933932563017313054187328842620219291572818766268178751411814560562534443426266396400495371407624162345901468773333852250822392143444872355448117811583996009775475129299419544905929790;
(C) \(36010656024371816954[189 digits]29299419544905929790\)

明文M,其中x為19位密碼
(%i12) M:B+x;
(M) \(x+79099116111098101114[151 digits]00000000000000000000\)

產生方程式p(x)≡(B+x)^e-C(mod N)
(%i13) px:M^e-C;
(px) \((x+79099116111098101114[151 digits]00000000000000000000)^3\)
   \(-36010656024371816954[189 digits]29299419544905929790\)

方程式p(x)同餘N
(%i14) px:polymod(px,N);
(px) \(x^3\)
   \(+23729734833329430334[152 digits]00000000000000000000x^2\)
   \(+57518597415676200644[189 digits]30736530413029557356x\)
   \(-78610106704918417037[189 digits]64951518554580927445\)

參數h
(%i15) h:3;
(h) \(3\)

呼叫Coppersmith_Howgrave副程式,找符合p(x)≡0(mod N)的較小的解x
執行時間需1965秒(32分鐘)

(%i18)
showtime:true$
x:Coppersmith_Howgrave(px,N,h);
showtime:false$

Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes.
參數\(h=3\)
\(p(x)\)最高次方\(k=3\)
\(\displaystyle X=ceiling(\frac{1}{\sqrt{2}} {{(hk)}^{-1/(hk-1)}} {{N}^{(h-1)/(hk-1)}} )\)
\(\displaystyle =ceiling(\frac{1}{\sqrt{2}} 9^{\frac{-1}{8}} 17969491597941066732[190 digits]64831638288518852689^{\frac{1}{4}})\)
\(=1106212689453879191977235208036134814768946283886104135857\)

\(q_{uv}=N^{h−1−v}x^u p(x)^v=\)
\([32290262828847459190[419digits]60277520976882530721,\)
\(32290262828847459190[419digits]60277520976882530721x,\)
\(32290262828847459190[419digits]60277520976882530721x^2,\)
\(17969491597941066732[190digits]64831638288518852689(x^3+23729734833329430334[152digits]00000000000000000000x^2+57518597415676200644[189digits]30736530413029557356x−78610106704918417037[189digits]64951518554580927445),\)
\(17969491597941066732[190digits]64831638288518852689x(x^3+23729734833329430334[152digits]00000000000000000000x^2+57518597415676200644[189digits]30736530413029557356x−78610106704918417037[189digits]64951518554580927445),\)
\(17969491597941066732[190digits]64831638288518852689x^2(x^3+23729734833329430334[152digits]00000000000000000000x^2+57518597415676200644[189digits]30736530413029557356x−78610106704918417037[189digits]64951518554580927445),\)
\((x^3+23729734833329430334[152digits]00000000000000000000x^2+57518597415676200644[189digits]30736530413029557356x−78610106704918417037[189digits]64951518554580927445)^2,\)
\(x(x^3+23729734833329430334[152digits]00000000000000000000x^2+57518597415676200644[189digits]30736530413029557356x−78610106704918417037[189digits]64951518554580927445)^2,\)
\(x^2(x^3+23729734833329430334[152digits]00000000000000000000x^2+57518597415676200644[189digits]30736530413029557356x−78610106704918417037[189digits]64951518554580927445)^2]\)

用\(1106212689453879191977235208036134814768946283886104135857x\)取代\(x\),得到\(q_{uv}=\)
\([32290262828847459190[419digits]60277520976882530721,\)
\(35719898487071973003[476digits]68945401330960162897x,\)
\(39513804972403437655[533digits]07174654938138697729x^2,\)
\(17969491597941066732[190digits]64831638288518852689(13536796742957524728[132digits]22453052799644267793x^3+29038231098365304034[266digits]00000000000000000000x^2+63627802340810115187[246digits]11462962337597714092x−78610106704918417037[189digits]64951518554580927445),\)
\(19878079628677272620[247digits]72697393439425769473x(13536796742957524728[132digits]22453052799644267793x^3+29038231098365304034[266digits]00000000000000000000x^2+63627802340810115187[246digits]11462962337597714092x−78610106704918417037[189digits]64951518554580927445),\)
\(21989383927217453979[304digits]76931392169955293361x^2(13536796742957524728[132digits]22453052799644267793x^3+29038231098365304034[266digits]00000000000000000000x^2+63627802340810115187[246digits]11462962337597714092x−78610106704918417037[189digits]64951518554580927445),\)
\((13536796742957524728[132digits]22453052799644267793x^3+29038231098365304034[266digits]00000000000000000000x2+63627802340810115187[246digits]11462962337597714092x−78610106704918417037[189digits]64951518554580927445)^2,\)
\(1106212689453879191977235208036134814768946283886104135857x(13536796742957524728[132digits]22453052799644267793x^3+29038231098365304034[266digits]00000000000000000000x^2+63627802340810115187[246digits]11462962337597714092x−78610106704918417037[189digits]64951518554580927445)^2,\)
\(12237065143087845640[75digits]14878644880713124449x^2(13536796742957524728[132digits]22453052799644267793x^3+29038231098365304034[266digits]00000000000000000000x^2+63627802340810115187[246digits]11462962337597714092x−78610106704918417037[189digits]64951518554580927445)^2]\)

產生矩陣
\(M=\left[\matrix{32290262828847459190[419 digits]60277520976882530721 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
0 & 35719898487071973003[476 digits]68945401330960162897 & 0 & 0 & 0 & 0 & 0 & 0 & 0\cr
0 & 0 & 39513804972403437655[533 digits]07174654938138697729 & 0 & 0 & 0 & 0 & 0 & 0\cr
-14125836519472822098[419 digits]94489721632952149605 & 11433592595586423031[476 digits]00952654252887393388 & 52180224974114632454[495 digits]00000000000000000000 & 24324935533561123862[361 digits]49738464971834145377 & 0 & 0 & 0 & 0 & 0\cr
0 & -15626179606991854661[476 digits]60211676569108886485 & 12647985215283616321[533 digits]86656469202955513516 & 57722427004923821310[552 digits]00000000000000000000 & 26908552357372882659[418 digits]46542924612696483089 & 0 & 0 & 0 & 0\cr
0 & 0 & -17285878168939820519[533 digits]81089654330431192645 & 13991361741171790418[590 digits]88089882508863743212 & 63853281218922005140[609 digits]00000000000000000000 & 29766582072559977503[475 digits]49821745201359022273 & 0 & 0 & 0\cr
61795488761586594662[418 digits]61228105756354228025 & -10003576662821081972[476 digits]14874260906612109880 & 40484972307212011736[532 digits]19137568143775384464 & 36952776573071059484[552 digits]95736854560233442230 & 84321886532206985153[571 digits]51737087375795677912 & 78616926430719870707[437 digits]00000000000000000000 & 18324486606014544982[303 digits]47263486203097090849 & 0 & 0\cr
0 & 68358953819071673294[475 digits]53451685880956792425 & -11066083444337370707[533 digits]78657042708931967160 & 44784990098426820113[589 digits]33285895980663125648 & 40877630355685238072[609 digits]16675173406681041110 & 93277940880617523876[628 digits]85134090008262090584 & 86967041623524387424[494 digits]00000000000000000000 & 20270779611300936552[360 digits]36453950823767472593 & 0\cr
0 & 0 & 75619542152448801923[532 digits]51332599109148483225 & -12241441928681489685[590 digits]25369415714902456120 & 49541724343946082466[646 digits]63054918145653160336 & 45219353414264099481[666 digits]97424893201642081270 & 10318524184826785550[686 digits]19237039307576470488 & 96204045008206368850[551 digits]00000000000000000000 & 22423793631144068882[417 digits]59771418125196067201}\right]\)

\(LLL\)化簡
\(B=\left[\matrix{-35743980059088545200[416 digits]80722642160047905681 & 46922824634222774487[417 digits]96446709945328871477 & 16364540563595223391[417 digits]91327750786549963386 & -97207301925654907852[417 digits]53799084107614558498 & -68006717288291680917[417 digits]14045799605521273218 & -22083850301737135483[417 digits]51281936303530818568 & 80777391656482090011[417 digits]81364384503413938164 & -18875467394270883798[417 digits]16922840533503730786 & 0\cr
-53855497698579115104[416 digits]22440422365250280904 & 74325972788911786534[417 digits]02667487696764782596 & -42360213040583351016[417 digits]52953633850159392540 & 93207789824932536615[417 digits]17899116640251965907 & 26743295137275436286[417 digits]30025365712179588699 & -19280506252185172185[417 digits]53869638507983632983 & -49522216738980310653[416 digits]09740058127199728661 & -54329652874359117291[417 digits]64740529713402819815 & 22423793631144068882[417 digits]59771418125196067201\cr
59886248145072283776[415 digits]00597316332236055074 & -13315128391293646051[417 digits]79917797014472050911 & 62558879042844919377[417 digits]09791573964335271861 & 11609344509786149688[418 digits]01042210268547527184 & -27368204832572340597[417 digits]17047835340290094121 & 17836124237718092338[417 digits]01896389102994872252 & -41032209045239051117[417 digits]16172892730225165900 & -59903924262576322974[417 digits]02209538630728871520 & -67271380893432206647[417 digits]79314254375588201603\cr
18422321777782777023[416 digits]59447344137439501243 & -21083022289790045344[417 digits]50420523383747574118 & -36876219378162584256[417 digits]55085598948970130728 & -12380026876101576575[418 digits]54404726405388353366 & 88756932911925724699[417 digits]97537235101170684352 & -14639498730317377843[418 digits]26252864402197471613 & -24797076405414559994[417 digits]60370312150796367236 & -16040594956631378629[418 digits]88876469069441734095 & 22423793631144068882[417 digits]59771418125196067201\cr
-59740829062319787233[416 digits]40688909484194485472 & 69491369706263632269[417 digits]58027265444373884189 & 12960931735222433006[418 digits]05407821747361781036 & 39543384198825880926[417 digits]32633257986499319708 & 14710427912295166891[418 digits]99414848522999747063 & -49840365686044385742[417 digits]35018273347131338824 & 20876577478866948183[417 digits]89058142685532409209 & 74627815624516244194[417 digits]75977705134307053965 & -44847587262288137765[417 digits]19542836250392134402\cr
-68384734181486838572[416 digits]00732056093284927437 & 91066074648706805896[417 digits]03099971016027027675 & -56710682936040096478[416 digits]32559138585047288553 & 72297457020480686195[417 digits]84446444836328742693 & -60533976691011414274[417 digits]31378847662774021892 & -12596396540470275328[418 digits]52090571729875618447 & -10880938062066902538[418 digits]67272557702486748080 & 21211756224520192677[418 digits]36650827112909148313 & 0\cr
-81250564085878561445[416 digits]34678304314010262958 & 10619954225570864725[418 digits]68561477549839159629 & 29714549780697273433[417 digits]69298528953401160635 & -43469171935032168882[417 digits]37163962147628359366 & -10442288961713937897[418 digits]86086266267518395545 & 49860675747404052367[416 digits]60024965193505807977 & -13253357916405795479[418 digits]68461980318400142027 & 13768422266804784107[417 digits]71514595120672325344 & 15696655541800848217[418 digits]18399926876372470407\cr
12609739358642155334[417 digits]57802314032806547340 & -17383608959896020481[418 digits]78499216381863868700 & 81673208107847127971[417 digits]29200832824127271546 & -20653954414963469692[417 digits]04471381311357994334 & -31161557914274171485[417 digits]97962853192070185042 & -84798118358121590160[417 digits]88845627108413875920 & 41678440330915146980[417 digits]79753567469752741441 & -85952558727161375791[417 digits]14248221183260863210 & 15696655541800848217[418 digits]18399926876372470407\cr
32200663351089791530[419 digits]57114456451584344136 & 12124879742313456102[418 digits]99114197642093654073 & -25995672476988127625[417 digits]61625883063609429154 & -39995121007223712365[416 digits]35899967467362592591 & -41263422151016244631[417 digits]84020433893341684519 & -41364356553922307668[417 digits]05151574811514451551 & 75825169982584058945[417 digits]71624326376214209503 & -73205120268630001090[417 digits]81663370246906550601 & 22423793631144068882[417 digits]59771418125196067201}\right]\)

產生不需要同餘\(N^2\)的方程式\(r(x)=\)
\(-35743980059088545200[416 digits]80722642160047905681\)
\(\displaystyle +46922824634222774487[417 digits]96446709945328871477( \frac{x}{1106212689453879191977235208036134814768946283886104135857})\)
\(\displaystyle +16364540563595223391[417 digits]91327750786549963386( \frac{x}{1106212689453879191977235208036134814768946283886104135857})^2\)
\(\displaystyle -97207301925654907852[417 digits]53799084107614558498( \frac{x}{1106212689453879191977235208036134814768946283886104135857})^3\)
\(\displaystyle -68006717288291680917[417 digits]14045799605521273218( \frac{x}{1106212689453879191977235208036134814768946283886104135857})^4\)
\(\displaystyle -22083850301737135483[417 digits]51281936303530818568( \frac{x}{1106212689453879191977235208036134814768946283886104135857})^5\)
\(\displaystyle +80777391656482090011[417 digits]81364384503413938164( \frac{x}{1106212689453879191977235208036134814768946283886104135857})^6\)
\(\displaystyle -18875467394270883798[417 digits]16922840533503730786( \frac{x}{1106212689453879191977235208036134814768946283886104135857})^7\)
\(\displaystyle +0(\frac{x}{1106212689453879191977235208036134814768946283886104135857})^8\)

\(r(x)=\)
\(-931166326910674526718530634530395511188484760951215019202x^7\)
\(+44081667002866521292[75 digits]22469878202438872436x^6\)
\(-13331579738644988581[132 digits]48018398665104447624x^5\)
\(-45414785555369089229[189 digits]85106015860347068418x^4\)
\(-71809678294997445547[246 digits]13523136087532093186x^3\)
\(+13372929188694233984[303 digits]93165215585922633914x^2\)
\(+42417543282194563777[360 digits]26324257495544510661x\)
\(-35743980059088545200[416 digits]80722642160047905681\)

\(= -(x-83113117101097109105115104032079115115105102114097103101)\)
\((931166326910674526718530634530395511188484760951215019202x^6\)
\(-43307745643175267650[75 digits]26182397092150127034x^5\)
\(+97321380036192344236[131 digits]32115288696559115190x^4\)
\(+46223653880907932101[189 digits]89490665635112272608x^3\)
\(+75651470252841928353[246 digits]55691765552926250594x^2\)
\(-70852996826996182688[302 digits]24287941312942141920x\)
\(-43006424624419143341[360 digits]20196969789558604581)\)

整數解為\([x=83113117101097109105115104032079115115105102114097103101]\)
Evaluation took 1965.2180 seconds (1977.6340 elapsed) using 132237.506 MB.}
(x) \([x=83113117101097109105115104032079115115105102114097103101]\)

將密碼x從個位數開始每3位數分隔出一個數字
(%i19) makelist(mod(floor(rhs(x[1])/1000^i),1000),i,length-1,0,-1);
(%o19) \([83,113,117,101,97,109,105,115,104,32,79,115,115,105,102,114,97,103,101]\)

每一個數字轉換成ASCII表示法
(%i20) makelist(ascii(i),i,%);
(%o20) \([S,q,u,e,a,m,i,s,h, ,O,s,s,i,f,r,a,g,e]\)

將list組合成字串,得到密碼
(%i21) simplode(%);
(%o21) \(Squeamish\) \(Ossifrage\)

TOP

2-1.兩個訊息有仿射關係
兩個訊息\(m_1\)和\(m_2=\alpha m_1+\beta\)有仿射關係(affine relation)
經由RSA加密,公鑰\(e=3\),得到密文\(\cases{c_1=m_1^3 \pmod{N} \cr c_2=m_2^3 \pmod{N}}\)
若已知\(c_1,c_2,\alpha,\beta,N\)就可以回復明文
\(\displaystyle \frac{\beta(c_2+2\alpha^3 c_1-\beta^3)}{\alpha(c_2-\alpha^3 c_1+2\beta^3)}=\frac{3\alpha^3\beta m_1^3+3\alpha^2 \beta^2 m_1^2+3\alpha \beta^3 m_1}{3 \alpha^3 \beta m_1^2+3\alpha^2 \beta^2 m_1+3 \alpha \beta^3}=m_1 \pmod{N}\)
上面的式子可以從\(m_1^3-c_1,(\alpha m_1+\beta)^3-c_2\)計算歐幾里得演算法得到最大公因式。
若\(\alpha=\beta=1\),則
\(\displaystyle \frac{(m+1)^3+2m^3-1}{(m+1)^3-m^3+2}=\frac{3m^3+3m^2+3m}{3m^2+3m+3}=m \pmod{N}\)


同樣RSA加密,換公鑰\(e=5\),得到密文\(\cases{c_1=m^5 \pmod{N}\cr c_2=(m+1)^5\pmod{N}}\)
\(P(m)=c_2^3-3c_1c_2^2+3c_1^2c_2-c_1^3+37c_2^2+176c_1c_2+37c_1^2+73c_2-73c_1+14\)
\(mP(m)=2c_2^3-1c_1c_2^2-4c_1^2c_2+3c_1^3+14c_2^2-88c_1c_2-51c_1^2-9c_2+64c_1-7\)
\(\displaystyle m=\frac{mP(m)}{P(m)}\)
令\(z\)為未知的訊息\(m\),則\(z\)滿足這兩個方程式\(\cases{z^5-c_1\equiv 0\pmod{N}\cr (z+1)^5-c_2\equiv 0\pmod{N}}\)
應用歐幾里得演算法找到最大公因式\(gcd(z^5-c_1,(z+1)^5-c_2)\in Z/N[z]\),得到線性多項式\(z-m\)。

參考資料:
Coppersmith D., Franklin M., Patarin J., Reiter M. (1996) Low-Exponent RSA with Related Messages. In: Maurer U. (eds) Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996. Lecture Notes in Computer Science, vol 1070. Springer, Berlin, Heidelberg.
https://link.springer.com/chapter/10.1007%2F3-540-68339-9_1
https://link.springer.com/content/pdf/10.1007/3-540-68339-9_1.pdf

顯示數字的全部位數會造成版面凌亂,將太長的數字縮短顯示
功能表選取,編輯/設定/Worksheet/Maximum displayed number of digits調整為80


多項式輾轉相除法副程式
(%i1)
GCD(fx1,fx2,var):=block([temp],
fx1:expand(fx1),
fx2:expand(fx2),
while hipow(fx2,var)#1 do
  (temp:fx2,
   print(fx1,"除以",fx2,"餘式",fx2:remainder(fx1,fx2,var)),
   fx1:temp
  ),
fx2
)$


根據密文c1,c2產生方程式
(%i3)
fx1:m1^3-c1;
fx2: (alpha*m1+beta)^3-c2;

(fx1) \(m_1^3-c_1\)
(fx2) \((\alpha m_1+\beta)^3-c_2\)

計算fx1和fx2輾轉相除法得到最大公因式
(%i4) GCD:GCD(fx1,fx2,m1);
\(m_1^3-c_1\)除以\(\alpha^3m_1^3+3\alpha^2\beta m_1^2+3\alpha\beta^2m_1-c_2+\beta^3\)餘式\(\displaystyle -\frac{3\alpha^2\beta m_1^2+3\alpha\beta^2m_1-c_2+\alpha^3c_1+\beta^3}{\alpha^3}\)
\(\alpha^3m_1^3+3\alpha^2\beta m_1^2+3\alpha\beta^2m_1-c_2+\beta^3\)除以\(\displaystyle -\frac{3\alpha^2\beta m_1^2+3\alpha\beta^2m_1-c_2+\alpha^3c_1+\beta^3}{\alpha^3}\)餘式\(\displaystyle\frac{(\alpha c_2-\alpha^4c_1+2\alpha\beta^3)m1-\beta c_2-2\alpha^3\beta c_1+\beta^4}{3\beta}\)
(GCD) \(\displaystyle\frac{(\alpha c_2-\alpha^4c_1+2\alpha\beta^3)m1-\beta c_2-2\alpha^3\beta c_1+\beta^4}{3\beta}\)

從最大公因式,解方程式得m1
(%i5) m1:solve(GCD,m1)[1];
(m1) \(\displaystyle m_1=\frac{\beta c_2+2 \alpha^3 \beta c_1-\beta^4}{\alpha c_2-\alpha^4 c_1+2 \alpha \beta^3}\)

範例取自Cryptanalytic Attacks on RSA
(%i10)
alpha:3;
beta:5;
N:7790302288510159542362475654705578362485767620973983941084402222135728725117099985850483876481319443405109322651368151685741199347755868542740942256445000879127232585749337061853958340278434058208881085485078737;
c1:132057584044937409231208389323398996878812486949811558724214983072091380989054308161277959733824865068687594213139826622055543700074552293693503940351187203266740911056806170880679978462212228231292575333924006;
c2:3565554769213310049242626511731772915727937147644912090997362096862084038123081043744658925329430451812652081858712220905928591327874274888835176225741122966452992998335410453929161733393892204730002674838955287;

(alpha) \(3\)
(beta) \(5\)
(N) \(77903022885101595423624756[159 digits]78434058208881085485078737\)
(c1) \(13205758404493740923120838[158 digits]62212228231292575333924006\)
(c2) \(35655547692133100492426265[159 digits]93892204730002674838955287\)

將\(\alpha,\beta,c_1,c_2\)代入
(%i11) m1:ev(m1,[alpha=alpha,beta=beta,c1=c1,c2=c2]);
(m1) \(\displaystyle m_1=\frac{\beta c_2+2 \alpha^3 \beta c_1-\beta^4}{\alpha c_2-\alpha^4 c_1+2 \alpha \beta^3}=\frac{16978832234349095472583935[158 digits]61164325860631773696362722}{51843405275386826203986806[103 digits]08706305166524791817361975}\)

明文m1,m2
(%i13)
m1:ratsimp(rhs(m1)),modulus:N;
m2:alpha*m1+beta;

warning: assigning 77903022885101595423624756[159 digits]78434058208881085485078737, a non-prime, to 'modulus'
(m1) \(200805001301070903002315180419000118050019172105011309190800151919090618010705\)
(m2) \(602415003903212709006945541257000354150057516315033927572400455757271854032120\)

驗算
(%i15)
is(power_mod(m1,3,N)=c1);
is(power_mod(m2,3,N)=c2);

(%o14) \(true\)
(%o15) \(true\)

清除m1,m2,alpha,beta,N,c1,c2設定
(%i16) kill(m1,m2,alpha,beta,N,c1,c2);
(%o16) \(done\)

根據密文c1,c2產生方程式
(%i18)
fx1:m1^5-c1;
fx2: (m1+1)^5-c2;

(fx1) \(m_1^5-c_1\)
(fx2) \((m_1+1)^5-c_2\)

計算fx1和fx2輾轉相除法得到最大公因式
(%i19) GCD:GCD(fx1,fx2,m1)
\(m_1^5-c_1\)除以\(m_1^5+5m_1^4+10m_1^3+10m_1^2+5m_1-c_2+1\)餘式\(-5m_1^4-10m_1^3-10m_1^2-5m_1+c_2-c_1-1\)
\(m_1^5+5m_1^4+10m_1^3+10m_1^2+5m_1-c_2+1\)除以\(-5m_1^4-10m_1^3-10m_1^2-5m_1+c_2-c_1-1\)餘式\(\displaystyle \frac{10m_1^3+15m_1^2+(c_2-c_1+9)m_1-2c_2-3c_1+2}{5}\)
\(-5m_1^4-10m_1^3-10m_1^2-5m_1+c_2-c_1-1\)除以\(\displaystyle \frac{10m_1^3+15m_1^2+(c_2-c_1+9)m_1-2c_2-3c_1+2}{5}\)餘式\(\displaystyle \frac{(2c_2-2c_1-7)m_1^2+(-3c_2-7c_1-7)m_1+2c_2-7c_1-2}{4}\)
\(\displaystyle \frac{10m_1^3+15m_1^2+(c_2-c_1+9)m_1-2c_2-3c_1+2}{5}\)除以\(\displaystyle \frac{(2c_2-2c_1-7)m_1^2+(-3c_2-7c_1-7)m_1+2c_2-7c_1-2}{4}\)餘式\(\displaystyle \frac{4c_2^3+(148-12c_1)c_2^2+(12c_1^2+704c_1+292)c_2-4c_1^3+148c_1^2-292c_1+56)m_1-8c_2^3+(4c_1-56)c_2^2+(16c_1^2+352c_1+36)c_2-12c_1^3+204c_1^2-256c_1+28}{20c_2^2+(-40c_1-140)c_2+20c_1^2+140c_1+245}\)
(GCD) \(\displaystyle \frac{4c_2^3+(148-12c_1)c_2^2+(12c_1^2+704c_1+292)c_2-4c_1^3+148c_1^2-292c_1+56)m_1-8c_2^3+(4c_1-56)c_2^2+(16c_1^2+352c_1+36)c_2-12c_1^3+204c_1^2-256c_1+28}{20c_2^2+(-40c_1-140)c_2+20c_1^2+140c_1+245}\)

從最大公因式,解方程式得m1
(%i20) m1:solve(GCD,m1)[1];
(m1) \(\displaystyle m_1=\frac{2c_2^3+(14-c_1)c_2^2+(-4c_1^2-88c_1-9)c_2+3c_1^3-51c_1^2+64c_1-7}{c_2^3+(37-3c_1)c_2^2+(3c_1^2+176c_1+73)c_2-c_1^3+37c_1^2-73c_1+14}\)

範例取自Cryptanalytic Attacks on RSA
(%i23)
c1:18796237015415790;
c2:7290180156009373;
N:35480779745861123;

(c1) \(18796237015415790\)
(c2) \(7290180156009373\)
(N) \(35480779745861123\)

將c1,c2代入
(%i24) m1:ev(m1,[c1=c1,c2=c2]);
(m1) \(\displaystyle m_1=\frac{2c_2^3+(14-c_1)c_2^2+(-4c_1^2-88c_1-9)c_2+3c_1^3-51c_1^2+64c_1-7}{c_2^3+(37-3c_1)c_2^2+(3c_1^2+176c_1+73)c_2-c_1^3+37c_1^2-73c_1+14}=-\frac{43297460062121981374915003596042374969361963498}{7019720390981513672602639591832073102833439091}\)

將分數m_1同餘N
(%i25) m1:ratsimp(rhs(m1)),modulus:N;
warning: assigning 35480779745861123, a non-prime, to 'modulus'
(m1) \(-16036924398274761\)

明文m1,m2
(%i27)
m1:mod(m1,N);
m2:m1+1;

(m1) \(19443855347586362\)
(m2) \(19443855347586363\)

驗算
(%i29)
is(power_mod(m1,5,N)=c1);
is(power_mod(m2,5,N)=c2);

(%o28) \(true\)
(%o29) \(true\)

TOP

2-2.兩個訊息有仿射關係
上一篇文章提到兩個訊息\(m_1\)和\(m_2=\alpha m_1+\beta\)有仿射關係的話就可以回復明文,但實務上兩個訊息的\(\alpha\)和\(\beta\)值不易得知。

改成明文\(M\)向左平移\(k\)位元,各加上隨機補綴值\(T_1\)和\(T_2\)(假設\(T_1<T_2\))後\(e=3\)次方同餘\(N\)得到密文\(c_1,c_2\)
\(c_1\equiv m_1^3=(2^kM+T_1)^3\pmod{N}\)
\(c_1\equiv m_2^3=(2^kM+T_2)^3\pmod{N}\)
若2個補綴值\(T_1\)和\(T_2\)很接近,設\(t\)為兩個補綴值的差,且\(t<N^{\frac{1}{9}}\)
\(t=T_2-T_1\),\(t=(2^kM+T_2)-(2^kM+T_1)\),\(t=m_2-m_1\),\(m_2=m_1+t\)
得到兩個同餘方程式,
\(\cases{c_1\equiv m_1^3\pmod{N}\cr c_2\equiv m_2^3\pmod{N}}\),\(\cases{m_1^3-c1\equiv 0\pmod{N}\cr (m_1+t)^3-c_2\equiv 0\pmod{N}}\)
利用Resultant消去共同變數\(m_1\),得到\(t\)的9次方程式。
\(Res_{m_1}(m_1^3-c_1,(m_1+t)^3-c_2)=t^9+(3c_1-3c_2)t^6+(3c_1^2+21c_1c_2+3c_2^2)t^3+(c_1-c_2)^3\equiv 0\pmod{N}\)
因為\(t<N^{\frac{1}{9}}\),可利用Coppersmith-Howgrave方法求得\(t\)較小的解。
再利用上一篇輾轉相除法求得\(m_1=2^kM+T_1\)的解,再將後面\(k\)位元刪除得到明文\(M\)。
\(\displaystyle m_1\equiv \frac{t(c_2+2c_1-t^3)}{c_2-c_1+2t^3}=\frac{t((m_1+t)^3+2m_1^3-t^3)}{(m_1+t)^3-m_1^3+2t^3}=\frac{t(3m_1^3+3m_1^2t+3m_1t^2)}{3m_1^2t+3m_1t^2+3t^3}\pmod{N}\)

本篇文章先介紹要如何計算Resultant(結式)。

參考資料:
D. Coppersmith. Finding a small root of a univariate modular equation. In Proceedings of Eurocrypt 1996, volume 1070 of Lecture Notes in Computer Science, pages 155–165. Springer, 1996.
https://link.springer.com/chapter/10.1007/3-540-68339-9_14
https://isc.tamu.edu/resources/preprints/1996/1996-02.pdf
https://canvas.mit.edu/courses/7 ... load?download_frd=1


公式

範例

設\(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\)和
\(g(x)=b_mx^m+b_{m-1}x^{m-1}+\ldots+b_0\)
是次數為\(n\)和\(m\)的多項式
設\(f(x)\)和\(g(x)\)的Sylvester矩陣為
\(Syl(f,g)=\left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right] \matrix{ \cr   \cr f(x)取m列\cr  \cr  \cr \cr g(x)取n列\cr }\)
則\(f(x)\)和\(g(x)\)的Resultant為Sylvester矩陣的行列式值
\(Res(f,g)=det(Syl(f,g))\)
\(Res(f,g)=\left|\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right|\)
\(f(x)=1x^3+2x^2+3x+4\)
\(g(x)=5x^2+6x+7\)
\(f(x)\)和\(g(x)\)的Sylvester矩陣為
\(Syl(f,g)=\left[\ \matrix{1&2 &3 &4 &0\cr 0 &1&2 &3 &4 \cr 5&6&7&0&0 \cr 0&5&6&7&0 \cr 0&0&5&6&7} \right] \matrix{f(x)取2列\cr \cr   \cr g(x)取3列 \cr }\)
\(f(x)\)和\(g(x)\)的Resultant為
\(Res(f,g)= \left|\ \matrix{1&2 &3 &4 &0\cr 0 &1&2 &3 &4 \cr 5&6&7&0&0 \cr 0&5&6&7&0 \cr 0&0&5&6&7} \right|=832 \)
超過3階行列式不能用交叉相乘方式計算,而降階方式計算量又太大,實務上可採用PA=LU分解,再個別計算矩陣\(P,L,U\)的行列式值,\(det(P)\cdot det(A)=det(L)\cdot det(U)\),進而得到矩陣\(A\)的行列式值。
參考資料:https://ccjou.wordpress.com/2012/04/13/palu-%E5%88%86%E8%A7%A3/
\(P=\left[ \matrix{1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&0&1&0\cr 0&0&1&0&0\cr 0&0&0&0&1}\right]\),\(det(P)=-1\)
\(L=\left[ \matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&5&1&0&0\cr 5&-4&0&1&0\cr 0&0&-\frac{5}{4}&\frac{1}{2}&1}\right]\),\(det(L)=1\cdot 1\cdot 1\cdot 1\cdot 1=1\)
\(U=\left[ \matrix{1&2&3&4&0\cr 0&1&2&3&4\cr 0&0&-4&-8&-20\cr 0&0&0&-8&16\cr 0&0&0&0&-26}\right]\),\(det(U)=1\cdot 1\cdot (-4)\cdot(-8)\cdot(-26)=-832\)
\(\displaystyle Res(f,g)=\frac{det(L)\cdot det(U)}{det(P)}=\frac{1\cdot (-832)}{-1}=832\)
判斷是否有共同根
若\(Res(f,g)=0\),則\(f,g\)有共同根
[證明]
設\(x=x_0\)是\(f(x)=0,g(x)=0\)的共同根,則\(f(x_0)=g(x_0)=0\)
\(\left[\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right]
\left[\matrix{x_0^{n+m-1}\cr x_0^{n+m-2}\cr \vdots \cr x_0^n \cr x_0^{n-1}\cr \vdots \cr x_0 \cr 1}\right]=\left[\matrix{f(x_0)x_0^{m-1}\cr f(x_0)x_0^{m-2}\cr \vdots \cr f(x_0)x_0 \cr f(x_0)\cr g(x_0)x_0^{n-1} \cr g(x_0)x_0^{n-2}\cr \vdots \cr g(x_0)x_0 \cr g(x_0)} \right]=0\)
\(Syl(f,g)x=0\)是齊次方程組
若\(x\)有非0解,則\(Syl(f,g)\)的行列式值要為0,得到
\(Res(f,g)=\left|\matrix{a_n&a_{n-1}&\ldots&\ldots&a_0&0&0\cr
0&a_n&a_{n-1}&\ldots&a_1&a_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&a_n&a_{n-1}&\ldots&a_0\cr
b_m&b_{m-1}&\ldots&\ldots&b_0&0&0\cr
0&b_m&b_{m-1}&\ldots&b_1&b_0&0\cr
0&0&\ddots&\ddots&\ddots&\ddots&\vdots\cr
0&0&0&b_m&b_{m-1}&\ldots&b_0}\right|=0\)
\(f(x)=(x^2-1)(x^2+x+2)=x^4+x^3+x^2-x-2\)
\(g(x)=(x^2-1)(x^3+x^2+x-1)=x^5+x^4-2x^2-x+1\)有共同根
設\(x=x_0\)是\(f(x)=0,g(x)=0\)的共同根,則\(f(x_0)=g(x_0)=0\)
\(\left[\matrix{1&1&1&-1&-2&0&0&0&0\cr
0&1&1&1&-1&-2&0&0&0\cr
0&0&1&1&1&-1&-2&0&0\cr
0&0&0&1&1&1&-1&-2&0\cr
0&0&0&0&1&1&1&-1&-2\cr
1&1&0&-2&-1&1&0&0&0\cr
0&1&1&0&-2&-1&1&0&0\cr
0&0&1&1&0&-2&-1&1&0\cr
0&0&0&1&1&0&-2&-1&1}\right]
\left[\matrix{x_0^8\cr x_0^7\cr x_0^6\cr x_0^5\cr x_0^4\cr x_0^3\cr x_0^2\cr x_0^1\cr 1} \right]=
\left[\matrix{f(x_0)\cdot x_0^4\cr f(x_0)\cdot x_0^3\cr f(x_0)\cdot x_0^2\cr f(x_0)\cdot x_0\cr f(x_0)\cr g(x_0)\cdot x_0^3\cr g(x_0)\cdot x_0^2\cr g(x_0)\cdot x_0\cr g(x_0)} \right]=0\)
\(Syl(f,g)x=0\)是齊次方程組
若\(x\)有非0解,則\(Syl(f,g)\)的行列式值要為0,得到
\(Res(f,g)=\left|\ \matrix{1&1&1&-1&-2&0&0&0&0\cr
0&1&1&1&-1&-2&0&0&0\cr
0&0&1&1&1&-1&-2&0&0\cr
0&0&0&1&1&1&-1&-2&0\cr
0&0&0&0&1&1&1&-1&-2\cr
1&1&0&-2&-1&1&0&0&0\cr
0&1&1&0&-2&-1&1&0&0\cr
0&0&1&1&0&-2&-1&1&0\cr
0&0&0&1&1&0&-2&-1&1}\right|=0\)
兩變數方項式消除共同變數
\(f(x,y)=0,g(x,y)=0\)為兩變數方程式,已知\(f(x)\)和\(g(x)\)有共同根,可利用Resultant消除共同變數
設\(f(x,y)=x^2y^2-25x^2+9=0\)
\(g(x,y)=4x+y=0\)
若要消去\(x\)變數,先以\(x\)為變數降冪排列
\(f(x,y)=(y^2-25)x^2+0x+9\),\(g(x,y)=4x+y\)
計算\(f(x,y)\)和\(g(x,y)\)的Resultant
\(Res_x(f,g)=\left|\ \matrix{y^2-25&0&9 \cr 4&y&0 \cr 0&4&y} \right|\ =y^4-25y^2+144=0\)
解得\(y=\pm 3,\pm 4\),代回\(g(x,y)=0\)
得\(\displaystyle (x,y)=(1,-4),(-1,4),(\frac{3}{4},-3),(-\frac{3}{4},3)\)

若要消去\(y\)變數,先以\(y\)為變數降冪排列
\(f(x,y)=x^2y^2+0y+(-25x^2+9),g(x,y)=y+4x\)
計算\(f(x,y)\)和\(g(x,y)\)的Resultant
\(Res_y(f,g)=\left|\ \matrix{x^2&0&-25x^2+9 \cr 1&4x&0 \cr 0&1&4x} \right|\ =16x^4-25x^2+9=0 \)
解得\(\displaystyle x=\pm \frac{3}{4},\pm 1\),代回\(g(x,y)=0\)
得\(\displaystyle (x,y)=(1,-4),(-1,4),(\frac{3}{4},-3),(-\frac{3}{4},3)\)
範例出處
http://buzzard.ups.edu/courses/2 ... ts-ups-434-2016.pdf


取多項式P的x的各項係數
(%i1)
coeffs(P,x):=block (local(l),l:[],
  for i from hipow(P,x) step -1 thru 0 do l:cons(coeff(P,x,i),l),
  reverse(l));

(%o1) coeffs(P,x):=block(local(l),l:[],for i from hipow(P,x) step -1 thru 0 do l:cons(coeff(P,x,i),l),reverse(l))

計算多項式P和Q的Sylvester矩陣
副程式出處http://www.lpthe.jussieu.fr/~talon/subresultant.mac

(%i2)
result(P,Q,x):=block(local(mat,len1,len2,ll1,ll2),
  len1:hipow(P,x)+1,
  len2:hipow(Q,x)+1,   /* assume len1 >= len2 */
  mat:zeromatrix(len1+len2-2,len1+len2-2),
  ll1:coeffs(P,x),
  ll2:coeffs(Q,x),
  for i from 1 thru len2-1 do (
    for j from i thru i+len1-1 do (
      mat[i,j]:ll1[j-i+1])),
  for i from len2 thru len2+len1-2 do (
    for j from i-len2+1 thru i do (
       mat[i,j]:ll2[j-i+len2])),
  mat)$


第2個例子
(%i5)
f:x^3+2*x^2+3*x+4;
g:5*x^2+6*x+7;
result(f,g,x);

(f) \(x^3+2x^2+3x+4\)
(g) \(5x^2+6x+7\)
(%o5) \(\left[\matrix{1&2&3&4&0\cr
0&1&2&3&4\cr
5&6&7&0&0\cr
0&5&6&7&0\cr
0&0&5&6&7}\right]\)

計算LU分解
(%i6) [P,L,U]:get_lu_factors(lu_factor(%,generalring));
(%o6) \([\left[\matrix{1&0&0&0&0\cr 0&1&0&0&0\cr 0&0&0&1&0\cr 0&0&1&0&0\cr 0&0&0&0&1} \right],\left[\matrix{\displaystyle 1&0&0&0&0\cr 0&1&0&0&0\cr 0&5&1&0&0\cr 5&-4&0&1&0\cr 0&0&-\frac{5}{4}&\frac{1}{2}&1} \right],\left[\matrix{1&2&3&4&0\cr 0&1&2&3&4\cr 0&0&-4&-8&-20\cr 0&0&0&-8&16\cr 0&0&0&0&-26} \right]]\)

計算矩陣P,L,U的行列式值
(%i9)
detP:determinant(P);
detL:determinant(L);
detU:determinant(U);

(detP) \(-1\)
(detL) 1
(detU) \(-832\)

計算行列式值
(%i10) detL*detU/detP;
(%o10) 832

第3個例子
(%i14)
f:x^4+x^3+x^2-x-2;
g:x^5+x^4-2x^2-x+1;
result(f,g,x);
determinant(%);

(f) \(x^4+x^3+x^2-x-2\)
(g) \(x^5+x^4-2*x^2-x+1\)
(%o13) \(\left[\matrix{1&1&1&-1&-2&0&0&0&0\cr
0&1&1&1&-1&-2&0&0&0\cr
0&0&1&1&1&-1&-2&0&0\cr
0&0&0&1&1&1&-1&-2&0\cr
0&0&0&0&1&1&1&-1&-2\cr
1&1&0&-2&-1&1&0&0&0\cr
0&1&1&0&-2&-1&1&0&0\cr
0&0&1&1&0&-2&-1&1&0\cr
0&0&0&1&1&0&-2&-1&1}\right]\)
(%o14) \(0\)

第4個例子
(%i16)
f:x^2*y^2-25*x^2+9;
g:4*x+y;

(f) \(x^2y^2-25x^2+9\)
(g) \(y+4x\)

消掉共同變數x
(%i19)
result(f,g,x);
determinant(%);
ratsimp(%);

(%o17) \(\left[\matrix{y^2-25&0&9\cr 4&y&0\cr 0&4&y}\right]\)
(%o18) \(y^2(y^2-25)+144\)
(%o19) \(y^4-25y^2+144\)

先解出y
(%i20) solve(%,y);
(%o20) \([y=-4,y=4,y=-3,y=3]\)

將y代回g(x,y)=0求x
(%i21) map(lambda([y],[solve(ev(g,y),x)[1],y]),%);
(%o21) \(\displaystyle [[x=1,y=-4],[x=-1,y=4],[x=\frac{3}{4},y=-3],[x=-\frac{3}{4},y=3]]\)

消掉共同變數y
(%i23)
result(f,g,y);
determinant(%);

(%o22) \(\left[\matrix{x^2&0&9-25x^2\cr 1&4x&0\cr 0&1&4x}\right]\)
(%o23) \(16x^4-25x^2+9\)

先解出x
(%i24) solve(%,x);
(%o24)  \(\displaystyle [x=-1,x=1,x=-\frac{3}{4},x=\frac{3}{4}]\)

將x代回g(x,y)=0求y
(%i25) map(lambda([x],[x,solve(ev(g,x),y)[1]]),%);
(%o25) \(\displaystyle [[x=-1,y=4],[x=1,y=-4],[x=-\frac{3}{4},y=3],[x=\frac{3}{4},y=-3]]\)

第1個例子
(%i30)
f:m1^3-c1;
g: (m1+t)^3-c2;
result(f,expand(g),m1);
determinant(%);
ratsimp(%);

(f) \(m1^3-c1\)
(g) \((t+m1)^3-c2\)
(%o28) \(\left[\matrix{1&0&0&-c1&0&0\cr 0&1&0&0&-c1&0\cr 0&0&1&0&0&-c1\cr 1&3t&3t^2&t^3-c2&0&0\cr 0&1&3t&3t^2&t^3-c2&0\cr 0&0&1&3t&3t^2&t^3-c2}\right]\)
(%o29) \((t^3-c2)^3+c1((t^3-c2)^2+c1(10t^3-c2)-9t^3(t^3-c2))+c1((t^3-c2)^2-c1(8t^3+c2)+c1(t^3-c2+c1))+c1(3t^2(9t^4-3t(t^3-c2))-(t^3-c2)(8t^3+c2))\)
(%o30) \(t^9+(3c1-3c2)t^6+(3c2^2+21c1c2+3c1^2)t^3-c2^3+3c1c2^2-3c1^2c2+c1^3\)

也可以使用maxima內建指令計算resultant
(%i31) resultant(f,g,m1);
(%o31) \(t^9+c1(3t^6+21c2t^3+3c2^2)-3c2t^6+c1^2(3t^3-3c2)+3c2^2t^3-c2^3+c1^3\)

整理成t的多項式
(%i32) ratsimp(%);
(%o32) \(t^9+(3c1-3c2)t^6+(3c2^2+21c1c2+3c1^2)t^3-c2^3+3c1c2^2-3c1^2c2+c1^3\)

TOP

2-3.兩個訊息有仿射關係
設明文\(M\)乘\(10^5\)倍,各加上隨機補綴值\(T_1\)和\(T_2\)(假設\(0\le T_1,T_2<10^5,T_1<T_2\))後\(e=3\)次方同餘\(N\)得到密文\(c_1,c_2\)。
\(c1=1881676371789154860897069000\)
\(c2=1881678004162711039676405223\)
\(N=54957464841358314276864542898551\)
若2個補綴值\(T_1\)和\(T_2\)很接近,設\(t\)為兩個補綴值的差,\(t\)未知但足夠小(\(t<N^{\frac{1}{9}}\))。
將密文\(c_1,c_2\),公鑰\(N\)代入9次同餘方程式
\(t^9+(3c_1-3c_2)t^6+(3c_1^2+21c_1c_2+3c_2^2)t^3+(c_1-c_2)^3\equiv 0\pmod{N}\)

雖然論文說能找到比\(N^{\frac{1}{9}}=3362\)還小的解,但以Coppersmith_Howgrave()副程式精算的上界\(X\)卻小很多。
\(\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)}N^{(h-1)/(hk-1)})\)
設\(h=3\),9次方程式\(k=9\),計算出\(X=172\)
而且會產生\(27 \times 27\)的超大矩陣,導致LLL化簡的時間大幅增加還無法求得較小的解。

換另一個作法,令\(t^3=x\),先解3次同餘方程式,不僅Coppersmith_Howgrave()副程式精算的上界\(X\)提高很多。
\(x^3+(3c_1-3c_2)x^2+(3c_1^2+21c_1c_2+3c_2^2)x+(c_1-c_2)^3\equiv 0\pmod{N}\)
設\(h=3\),3次方程式\(k=3\),計算出\(X=46260610\)
而且產生\(9\times 9\)較小的矩陣,LLL化簡的時間變得更短了

所得到的較小\(x\)的解,再解一次3次同餘方程式,得到兩個補綴值的差\(t\)。
\(t^3-x\equiv 0\pmod{N}\)

再將密文\(c_1,c_2\),補綴值的差\(t\),公鑰\(N\)代入以下公式得到有補綴值的\(m_1\),再將後5位補綴值刪除得到明文\(M\)。
\(\displaystyle m_1\equiv \frac{t(c_2+2c_1-t^3)}{c_2-c_1+2t^3}\pmod{N}\)


請下載LLL.zip,解壓縮後將LLL.mac放到C:\maxima-5.46.0\share\maxima\5.46.0\share目錄下
要先載入LLL.mac才能使用Coppersmith_Howgrave指令

(%i1) load("LLL.mac");
(%o1) C:/maxima-5.46.0/share/maxima/5.46.0/share/LLL.mac

已知密文\(c_1,c_2\),公鑰\(N\)
(%i4)
c1:1881676371789154860897069000;
c2:1881678004162711039676405223;
N:54957464841358314276864542898551;

(c1) 1881676371789154860897069000
(c2) 1881678004162711039676405223
(N) 54957464841358314276864542898551

9次同餘方程式
(%i5) fx:x^9+(3*c1-3*c2)*x^6+(3*c1^2+21*c1*c2+3*c2^2)*x^3+(c1-c2)^3;
(fx) \(x^9-4897120668536338008669x^6+95599144073213399280057649148373498671072396308207166187x^3\)
\(-4349693466736349905369332025355097289037604766707550608234921567\)

同餘方程式係數同餘N,讓係數變小
(%i6) fx:polymod(fx,N);
(fx) \(x^9-4897120668536338008669x^6-1516451737447758219766669752498x^3-21000738238808374545647388458802\)

參數h
(%i7) h:3;
(h) 3

利用Coppersmith_Howgrave方法解9次同餘方程式,執行時間需2262秒(37分鐘)
但執行結果無法求得較小的整數解,故省略執行過程

(%i10)
showtime:true$
Coppersmith_Howgrave(fx,N,h);
showtime:false$

...
整數解為[]
Evaluation took 2262.6870 seconds (2264.0150 elapsed) using 420496.373 MB.
(%o9) []

令t^3=x,化簡成3次同餘方程式
(%i11) fx:x^3+(3*c1-3*c2)*x^2+(3*c1^2+21*c1*c2+3*c2^2)*x+(c1-c2)^3;
(fx) \(x^3-4897120668536338008669x^2+95599144073213399280057649148373498671072396308207166187x\)
\(-4349693466736349905369332025355097289037604766707550608234921567\)

同餘方程式係數同餘N,讓係數變小
(%i12) fx:polymod(fx,N);
(fx) \(x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802\)

利用Coppersmith_Howgrave方法解3次同餘方程式,執行時間需43秒
(%i15)
showtime:true$
X:Coppersmith_Howgrave(fx,N,h);
showtime:false$

Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes.
參數\(h=3\)
\(p(x)\)最高次方\(k=3\)
\(\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)}N^{(h-1)/(hk-1)})=ceiling(\frac{1}{\sqrt{2}}9^{-1/8}54957464841358314276864542898551^{1/4})=46260610\)
\(q_uv=N^{h-1-v} x^u p(x)^v =\) \([3020322941789135243826751301254310584993059920451586964677899601,\)
\(3020322941789135243826751301254310584993059920451586964677899601x,\)
\(3020322941789135243826751301254310584993059920451586964677899601x^2,\)
\(54957464841358314276864542898551(x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802),\)
\(54957464841358314276864542898551x(x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802),\)
\(54957464841358314276864542898551x^2(x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802),\)
\((x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802)^2,\)
\(x(x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802)^2,\)
\(x^2(x^3-4897120668536338008669x^2-1516451737447758219766669752498x-21000738238808374545647388458802)^2]\)
用\(46260610x\)取代\(x\),得到\(q_{uv}=\) \([3020322941789135243826751301254310584993059920451586964677899601,\)
\(139721981684159887751924249514318172791235797686641888454048089061016610x,\)
\(6463624103118063744935544456324562407407970654820642611436221569296955598732100x^2,\)
\(54957464841358314276864542898551(98999742604948264981000x^3-10480053887972286407738186731512534900x^2-70151982409893138378920200419106503780x-21000738238808374545647388458802),\)
\(2542365847614788847019462641858137376110x(98999742604948264981000x^3-10480053887972286407738186731512534900x^2-70151982409893138378920200419106503780x-21000738238808374545647388458802),\)
\(117611394953827177084317023684568968482648027100x^2(98999742604948264981000x^3-10480053887972286407738186731512534900x^2-70151982409893138378920200419106503780x-21000738238808374545647388458802),\)
\((98999742604948264981000x^3-10480053887972286407738186731512534900x^2-70151982409893138378920200419106503780x-21000738238808374545647388458802)^(2),\)
\(46260610x(98999742604948264981000x^3-10480053887972286407738186731512534900x^2-70151982409893138378920200419106503780x-21000738238808374545647388458802)^(2),\)
\(2140044037572100x^2(98999742604948264981000x^3-10480053887972286407738186731512534900x^2-70151982409893138378920200419106503780x-21000738238808374545647388458802)^(2)]\)
產生矩陣\(M=\left[ \matrix{
3020322941789135243826751301254310584993059920451586964677899601&0&0&0&0&0&0&0&0\cr
0&139721981684159887751924249514318172791235797686641888454048089061016610&0&0&0&0&0&0&0\cr
0&0&6463624103118063744935544456324562407407970654820642611436221569296955598732100&0&0&0&0&0&0\cr
-1154147333401880370164435877744830779893335235336308145728995902&-3855375106843289059874469643405077531431008453876682145059536838022780&-575957193083777435966023818707724430220694882620408968134835546929900&5440774873514967046498526949032608069078072148942531000&0&0&0&0&0\cr
0&-53391559673044361070832604010361296224641422921151169969392245114020220&-178352004221385726316119489130401363701292623991492180806562660444404996695800&-26644131085943325292024201127948743853911779893898517315388054650660801239000&251693564521475219700920220763687359166473755234092339003910000&0&0&0&0\cr
0&0&-2469926119326432700196969469407759883742609255600435024997766588244094929534200&-8250672510003878744676740400060736629653654574347063094341880675381046234195692438000&-1232573756955700653437467678941596939415709824077480689105413794852905568404895790000&11643497827837801763248586973862843084330167466119804398647668985100000&0&0&0\cr
441031006574948269107459443949256719868815747806770028851275204&2946486839047310595109751478204161934049771268347937188112057574543120&4921301076215693158799367543245210199690179969531456795727185981205628668000&1470393112007528062187159841915196407503917007629683675986668119372838320000&109831529494789146606929429768530109268611975609482301299443587987461650000&-2075045274790487347904810593080778841186998131216420673800000&9800949035846008678895673107522190930361000000&0&0\cr
0&20402363393071117647355229427353424907730536471147343664377590214914440&136306278531300406989240120330126235607922189234249266563748531753485202503200&227662389779394457098885610164724803415889536400306605558985017074020917615167480000&68021282301266572748895948454500554080939778162323820958185619069740318114575200000&5080873551661937743415985648044361658132643844999773042316053040888648280606500000&-95992860189425566911358759970378608468403657618931662386599018000000&453397880977148227551007964314572140974967380210000000&0\cr
0&0&943825776005139675748417799999320121820808332782523517793742593671973092208400&6305611591687860920570511402945041036226201306511803963291610965520595093771558952000&10531801025252553016013278646442369888149133646495387760188037870704622801637392876962800000&3146706012238795427973303402033752877122263511053778975056451231393819657574298642872000000&235044309832747753792446979829777477365827565182434950799096426463863811536307859965000000&-4440688268007542274915272165073296358699518927682926250318126398080980000000&20974462546710273066928434544050339130507985738616528100000000}\right]\)
LLL化簡\(B=\left[ \matrix{
53771676921999198037128719975410481845009948321580737058118762&50209380384868519769271355772363021078882998018525986723096380&107113429339000465042631199484653568414097906566121374434204800&2566158289017059510580947933126354061025546078929008772549000&-39201258910319328503256252507864134476510009966583646884840000&-82244768124108488515911014612606850013994967332618611133000000&-103326720791445976823937028600478023227439055205294880233000000&37553747697339884108136344819118362708215810289041024760000000&-41948925093420546133856869088100678261015971477233056200000000\cr
145771311156080366680612542702670552709050420859148668552121201&-102701813735090026820390486307494510321459974199722868939788630&55690597658188982675500688460805070018767816245101070397610800&-3690675191418901829302352712732398605405813417421315444807000&-34161730786036250811133667107244245173497899683329768637600000&105158149470961723712865498187081390865505368625840232003900000&-83943991120073620894214705274131521444270306664078709465000000&-94290002110963796909267598874077903051034921264274818610000000&0\cr
22520257569452314079351935267514264370266330796992552972684997&-98310513164562058062910678303618723610419189844159039543246600&-59216755675973590492737933555662165421890387526607433485560200&210122354709341487106669358644005820317705567891681532969573000&-13547462576968605065539206672838828517502007656710102017580000&23570869821207231876579884845247791136173699754579501358900000&-40641684543556222622266012007342445503983888770262907798000000&-86958932882212997194203757223689795368058144049335172070000000&41948925093420546133856869088100678261015971477233056200000000\cr
169015127177354263666121860022442922657381338158956682760146316&-44086339219025359808922118654836582121338928607019431900103130&-55743427083965516899322695992901696889154913782390199199450100&-99213756448548832412671199081590293096668700399267187647555000&-13681783036472695133702522618982681148717527439219162384970000&-15336537742431604945023054843850719026627918786732999429600000&64672345006900325309865538762091565046333246270689577751000000&-71951332896677550420724086465591699219582263948746051800000000&62923387640130819200785303632151017391523957215849584300000000\cr
-111109391058117478677425543043666767886469428988351808979162264&68706199548070844584789292006960471026818898889658819004932390&114242801459017508543027293838247104016630443508968997031447000&-70229925147280191228538106815486527561582710206602914483698000&-108177296750967223863314840883237590333571940265343423758290000&21114534120011920453814163485385935919207972703328940545600000&-34780235497393011659779194620008032778904564753918395174000000&44536869417475438776116536835516252809621296087125152680000000&83897850186841092267713738176201356522031942954466112400000000\cr
32124330345979841767629832716536687416322338071176926036776624&27164161165425888332075134727974947827481095848187898522695730&-79639511287230298148663766719580830450559479484044659434682900&-51041393060884297450399678845972688262211525661235763838740000&-120857089745132822141399493042839109949450984516626943707450000&220466029767922832433728342036436413650585457627045150329700000&-42081776027182400361358030886271577560506458471894525675000000&58148929768074224345419762221788597120206147540057861770000000&-41948925093420546133856869088100678261015971477233056200000000\cr
-118279971490860306266688062364858934470851326591670377750842105&186394623214470748860705331927751369982342478110034345905919190&-5844542338433954468770696410970613047578620794759879329291700&-31690810413815853326709322936928777204830797244545090618294000&36631940618043663684819094023611438217838817287345595588310000&14670122074875238001436616319545787277339265229080644956400000&-87941416624880050595555558070529584290459598827529416836000000&-58985200396438287348022673963584538334771708074420956690000000&62923387640130819200785303632151017391523957215849584300000000\cr
-67402575181872320450341662740231249645051561595949203267092646&81687875727598274014317606405009186128237310267665643776123970&-60606071715445114152730683837370692931748434259046928181917500&118448345919188327186093480437680808892299725583302023014092000&5659950991122719764062671142382391292964286805841933824120000&61863373560034972019278274616457949997753618484681115789000000&87493980444210846078712251695585839215963143393159467086000000&-110345238655812995600366365368792036283900354142468092020000000&-125846775280261638401570607264302034783047914431699168600000000\cr
391536656683468813127560730295755766606487863741754115343991921&447549940911495565399271813369673072505177321547345359598698170&345431307115038022995995779076001023195500573892855741305309800&330776015310331719481270882134135987680304349298242517737362000&334129783160230133456909028931418304394164386380225530980110000&298169048606388347296126093056185837124427112397441890970200000&317606145581069503748397520803157118676806368270962392206000000&313838224166290677083070069124989059103490292778965585030000000&440463713480915734405497125425057121740667700510947090100000000}\right]\)
產生不需要同餘\(N^2\)的方程式
\(r(x)=53771676921999198037128719975410481845009948321580737058118762 \)
\(\displaystyle +50209380384868519769271355772363021078882998018525986723096380 ( \frac{x}{46260610} ) \)
\(\displaystyle +107113429339000465042631199484653568414097906566121374434204800 ( \frac{x}{46260610} )^2 \)
\(\displaystyle +2566158289017059510580947933126354061025546078929008772549000 (\frac{x}{46260610})^3 \)
\(\displaystyle -39201258910319328503256252507864134476510009966583646884840000 (\frac{x}{46260610})^4 \)
\(\displaystyle -82244768124108488515911014612606850013994967332618611133000000 (\frac{x}{46260610})^5 \)
\(\displaystyle -103326720791445976823937028600478023227439055205294880233000000 (\frac{x}{46260610})^6 \)
\(\displaystyle +37553747697339884108136344819118362708215810289041024760000000 (\frac{x}{46260610})^7 \)
\(\displaystyle -41948925093420546133856869088100678261015971477233056200000000 (\frac{x}{46260610})^8 \)

\(r(x)= -2x^8+82827356x^7-10542521995935153x^6-388196401064276818832330x^5-8559622143684325599618510860324x^4\)
\(+25920858191087824461843813370140390129x^3+50051974379238314010577044980314319102425126688x^2+1085359237261863165428889843267588150672526756965072158x+53771676921999198037128719975410481845009948321580737058118762\)
\( = -(x-45499293)(2x^7+8171230x^6+10914307183875543x^5+884789661515435025323429x^4+48816926196345927839271626696021x^3\)
\(+2195214770175831075654032836258741023024x^2+49828745646919485619110961668243162515263595344x+1181813460749801058164326201187576295856068539825019634) \)
整數解為\([x=45499293]\)
Evaluation took 43.1100 seconds (43.1220 elapsed) using 5541.766 MB.
(X) \([x=45499293]\)

再解一次3次同餘方程式
(%i16) fx:x^3-rhs(X[1]);
(fx) \(x^3-45499293\)

利用Coppersmith_Howgrave方法解3次同餘方程式,執行時間需0.328秒
(%i19)
showtime:true$
X:Coppersmith_Howgrave(fx,N,h);
showtime:false$

Evaluation took 0.0000 seconds (0.0000 elapsed) using 0 bytes.
參數\(h=3\)
p(x)最高次方\(k=3\)
\(\displaystyle X=ceiling(\frac{1}{\sqrt{2}}(hk)^{-1/(hk-1)}N^{(h-1)/(hk-1)})=ceiling(\frac{1}{\sqrt{2}}9^{-1/8}54957464841358314276864542898551^{1/4})=46260610\)
\(q_{uv}=N^{h-1-v} x^u p(x)^v =\)
\([3020322941789135243826751301254310584993059920451586964677899601,\)
\(3020322941789135243826751301254310584993059920451586964677899601x,\)
\(3020322941789135243826751301254310584993059920451586964677899601x^2,\)
\(54957464841358314276864542898551(x^3-45499293),\)
\(54957464841358314276864542898551x(x^3-45499293),\)
\(54957464841358314276864542898551x^2(x^3-45499293),\)
\((x^3-45499293)^2,\)
\(x(x^3-45499293)^2,\)
\(x^2(x^3-45499293)^2]\)
用\(46260610x\)取代\(x\),得到\(q_uv=\)
\([3020322941789135243826751301254310584993059920451586964677899601,\)
\(139721981684159887751924249514318172791235797686641888454048089061016610x,\)
\(6463624103118063744935544456324562407407970654820642611436221569296955598732100x^2,\)
\(54957464841358314276864542898551(98999742604948264981000x^3-45499293),\)
\(2542365847614788847019462641858137376110x(98999742604948264981000x^3-45499293),\)
\(117611394953827177084317023684568968482648027100x^2(98999742604948264981000x^3-45499293),\)
\((98999742604948264981000x^3-45499293)^2,\)
\(46260610x(98999742604948264981000x^3-45499293)^2,\)
\(2140044037572100x^2(98999742604948264981000x^3-45499293)^2] \)
產生矩陣\(M=\left[ \matrix{
3020322941789135243826751301254310584993059920451586964677899601&0&0&0&0&0&0&0&0\cr
0&139721981684159887751924249514318172791235797686641888454048089061016610&0&0&0&0&0&0&0\cr
0&0&6463624103118063744935544456324562407407970654820642611436221569296955598732100&0&0&0&0&0&0\cr
-2500525795354160459269142958652241224443&0&0&5440774873514967046498526949032608069078072148942531000&0&0&0&0&0\cr
0&-115675848613818628883670707444457456909880090230&0&0&251693564521475219700920220763687359166473755234092339003910000&0&0&0&0\cr
0&0&-5351235319142904201522225965512143075699768000894840300&0&0&11643497827837801763248586973862843084330167466119804398647668985100000&0&0&0\cr
2070185663499849&0&0&-9008836591414248716424316866000&0&0&9800949035846008678895673107522190930361000000&0&0\cr
0&95768051606757749647890&0&0&-416754276109143908313505917054448260000&0&0&453397880977148227551007964314572140974967380210000000&0\cr
0&0&4430288485840093620938676612900&0&0&-19279307032917423776366854961548179721038600000&0&0&20974462546710273066928434544050339130507985738616528100000000}\right]\)
LLL化簡\(B=\left[ \matrix{
2070185663499849&0&0&-9008836591414248716424316866000&0&0&9800949035846008678895673107522190930361000000&0&0\cr
0&95768051606757749647890&0&0&-416754276109143908313505917054448260000&0&0&453397880977148227551007964314572140974967380210000000&0\cr
-2500525795354160459269142958652241224443&0&0&5440774873514967046498526949032608069078072148942531000&0&0&0&0&0\cr
0&0&4430288485840093620938676612900&0&0&-19279307032917423776366854961548179721038600000&0&0&20974462546710273066928434544050339130507985738616528100000000\cr
0&-115675848613818628883670707444457456909880090230&0&0&251693564521475219700920220763687359166473755234092339003910000&0&0&0&0\cr
3020322941789135243826751301254310584993059920451586964677899601&0&0&0&0&0&0&0&0\cr
0&0&-5351235319142904201522225965512143075699768000894840300&0&0&11643497827837801763248586973862843084330167466119804398647668985100000&0&0&0\cr
0&139721981684159887751924249514318172791235797686641888454048089061016610&0&0&0&0&0&0&0\cr
0&0&6463624103118063744935544456324562407407970654820642611436221569296955598732100&0&0&0&0&0&0}\right]\)
產生不需要同餘\(N^2\)的方程式
\(\displaystyle r(x)= 2070185663499849 + 0 ( \frac{x}{46260610} ) + 0 (\frac{x}{46260610})^2 \)
\(\displaystyle -9008836591414248716424316866000 (\frac{x}{46260610})^3 + 0 (\frac{x}{46260610})^4 + 0 (\frac{x}{46260610})^5\)
\(\displaystyle +9800949035846008678895673107522190930361000000 (\frac{x}{46260610})^6 + 0 (\frac{x}{46260610})^7 + 0 (\frac{x}{46260610})^8 \)
\(r(x)=x^6-90998586x^3+2070185663499849=(x-357)^2(x^2+357x+127449)^2 \)
整數解為\( [x=357] \)
Evaluation took 0.3280 seconds (0.3280 elapsed) using 88.429 MB.
(X) \([x=357]\)

從密文\(c_1,c_2\),兩個補綴值的差\(t=T_2-T_1\)求得加上補綴值得明文\(m_1\)
(%i20) m1:t*(c2+2*c1-t^3)/(c2-c1+2*t^3);
(m1) \(\displaystyle \frac{t(5645030747741020761470543223-t^3)}{2t^3+1632373556178779336223}\)

將\(t\)值帶入\(m_1\)公式
(%i21) ev(m1,t=rhs(X[1]));
(%o21) \(1234567890\)

將後5位補綴值刪除,得到明文M
(%i22) M:floor(%/10^5);
(M) \(12345\)

TOP

 14 12
發新話題