ΥڡϤƤʥ֥åޡɲΥڡޤϤƤʥ֥åޡ Υڡlivedoor åפɲΥڡޤlivedoor å

ܼ

ȤˤŹ˴ؤڡǤϡ­ʤäꡢäҤ򤷤ƤꤹȤޤ塢ĽͽǤ

ŹΡذŹ浻ѤΤ٤ơ٤ȯ䤵Ƥޤ鿴ԸΰŹܤǤޤǰŹܤ˲٤ĩ路ĤĤޤƤޤäعβǺǤʻˤưŹ꤬ʤɤˤǤ

ذŹ浻ѤΤ٤ơ

̣򻲾ȤƤAmazonǤȯǤ

RSAŹȤ

RSAŹɽŪʸŹϤΤҤȤĤǤ롣ؿѤ뤳ȤǰŹ沽ǽȤƤ롣Ź沽Ǥʤ̾ʤɤˤѤǤ롣

RSAŹ

RSAŹ1977ǯR.L.RivestA.ShamirL.AdlemanˤäƹͰƤ줿RSAŹ̾Τϡ르ꥺγȯԤƬʸR.L.RivestA.ShamirL.AdlemanˤͳǤ롣

RSAŹλȤ

ꥹϼΥ르ꥺ¹Ԥ롣

12Ĥ礭ǿp,qN=pq׻롣

2GCD((p-1)(q-1),e)=1Ȥʤe֡

3ĥ桼åɤθ߽ˡˤꡢed~\equiv~1~\,~mod~\,~\(p-1\)\(q-1\)Ȥʤd롣

4pk=(N,e)ȤƸd̩Ȥݻ롣

Ź沽

ܥ֤ϸ(N,e)ʿʸm(ZZ)ϤȤơΤ褦˰Źʸc׻롣

c=me mod N

ꥹ̩dȰŹʸcϤȤƼΤ褦˷׻ʿʸm椹롣

ce mod N

ˤ줬mˤʤäƤ뤫ɤΤСŹϤλͤȤˤʤ롣

[]

ed1 (mod (p-1)(q-1))
(p-1)(q-1)|ed-1
p-1|ed-1
ed1 (mod p-1)


cd
(me)d
med
m mod pʢpǿǡxx1 (mod p-1)ߤȤǤդaФơaxa (mod p)פΩġ
cd-m0 (mod p)

Ʊͤˡcd-m0 (mod q)

ǡpqϸߤǤʤΤǡcd-mpqξdzڤ롣

cd-m0 (mod pq)
cdm (mod N)

[̾]

cd (mod N)
med (mod N)
m1+lߦ(N) (mod N);
m (mod N)

RSAŹΰ

СǤŪRSAŹʶʽŪRSAŹˤOW-CPAǤ롣

[]RSAŹɤRSA-OAEPŹ४饯ǥβIND-CCA2Ǥ롣

Nǰʬ򤬲ǽä

Nǰʬ򤬤ǤСRSAŹ椬ˤ뤳ȤϤ狼롣ʤʤСNǰǤp,q狼ȡed1 (mod (p-1)(q-1))פ̩d뤳ȤǤƤޤ

Ĥޤꡢ2Ĥǿp,qȤϡNǰʬ򤬺ˤʤ褦礭ͤˤʤФʤʤ׻ǽθ太ӥ르ꥺοͤȡp,qȤ512ӥåȰʾǿ˾ޤäơN1,024ӥåȰʾȤȤˤʤ롣

ǰʬ򥢥르ꥺη׻ץƥå׿δp,qΥӥåĹˤĤ

SchreeppelˤСΤ¤ǤäȤ®ǰʬ򥢥르ꥺȤäη׻ץƥå׿ϡΤ褦ˤʤȤ

T=\exp~\sqrt{\ln\(n\)\ln\(\ln\(n\)\)}

nǿΤȤGR(n)ˤΥпη׻ץƥå׿ƱǤAdlemanˡ

㡧p200ӥåȤĹȤСT=2.71011Ȥʤ롣Ĥޤꡢ11011ƥåסʤʤä1ƥåס˼¹ԤǤȤС֤η׻̤Ǥ롣
p664ӥåĹ10ʿ20ˤˤʤȡT=1.21023Ȥʤ롣Ĥޤꡢ1012֡ʡǯˤȤȤˤʤ롣

N200ȤȤϡpq줾100٤礭ǿɬפ롣RivestShamirAdlemanˡSolvey-StressenˡǤ롣

[]Nǰʬ򤹤뤿ɬפʷ׻̤ϼ̤Ǥ롣ϿΤդ뤤ˡѤη׻̤

NΥʥӥåȡMIPSǯ
5123104
102431011
204831020

ǿp,q

ǰʬФɸʤȤơpqˤĤƤ˼ͽ˻ߤ򹷤ƤȤ夵Ƥ롣

  1. p-1礭ǰr1ͭ롣ʤġq-1礭ǰr2ͭ롣
  2. p+1礭ǰr1ͭ롣ʤġq+1礭ǰr2ͭ롣
  3. r1-1礭ǰr1ͭ롣ʤġr2-1礭ǰr2ͭ롣
  4. pqĹ򡢤ۤοѤ롣
  5. GCD(p-1,q-1)Ͼ롣
  6. |p-q|ü˾ʤʤ褦ˤ롣

13ˤĤ

p-1礭ǰĤ褦ǿp򸫤Ĥˤϡޤǿp'롣
i˴ؤơp=i*p'+1 i=2,4,6,ġˡפpǿˤʤޤ³롣
ɸ򶯤ˤp'-1礭ǰĤ褦p'֤٤Ǥ롣

SimmonsNorrisϡpq򿵽ŤǤʤǰʬ򤷤ʤǤ⤳ˤǽ򼨤Ƥ롣
ɥС꡼ϰŹʸc0(=Me (mod N))ȸ(e,N)СiˤĤơci=cSUB{i-1}e (mod N)i=1,2,ġפη׻cịΤåˤʤޤǷ֤СmǤǽ롣

RivestˤСp-1礭ǰp'p'-1礭ǰp''Ĥ褦p硢μβɤΨ϶ˤƾȤȯ㤨С1090ʾǿˤĤƤϡΨϤۤ10-90Ǥ롣

6ˤĤ

pq礭Ƥ⡢|p-q|ü˾Ȥ˥եޡǰʬ򥢥르ꥺȤäơN=pqǰʬ򤹤뤳ȤưפˤʤäƤޤ

(N)=(p-1)(q-1)=pq-(p+q)+1=N-(p+q)+1
p+q=N-(N)+1

(p+q)2-4N=(p2+2pq+q2)-4pq=p2-2pq+q2=(p-q)2
p-q={(p+q)2-4N}

ǡɥС꡼N,p-qΤʤΤǡp,q뤳ȤǤƤޤ

ŪŹϤȤ

m=0ΰŹʸc=0m=1ΰŹʸc=1Ȥʤ롣ˤꡢm=0 or m=1Ǥ뤳Ȥˤ狼äƤ褦ʾϡưפ˲ɤǤƤޤĤޤꡢŪŹϤȤȤ

Ʊʿʸ2Ź沽ȡƱΰŹʸ

Ʊʿʸ2Ź沽ȡƱΰŹʸˤʤ롣ꡢƱʿʸ2Ź沽Ȥ¤狼äƤ롣RSAŹʳǤŪŹϤʤ鶦̤Ǥ롣

c˴ؤ䥳Ӥε椫餽бm˴ؤ䥳Ӥεʬ׻Ǥ

c˴ؤ䥳Ӥε椫餽бm˴ؤ䥳Ӥεʬ׻Ǥ롣

RSAŹξϡc=me mod NפġeפʤΤǡΤ褦˷׻Ǥ롣

(C/N)=(me/N)=(m/N)e=(m/N)

ǤդθȰȼ

[]BlakleyBlakeyBlakleyBorosh
ǤդθˤϾʤȤ9ĤʿʸϰŹ沽̩뤳ȤǤʤĤޤꡢǤդeNˤĤƤϾʤȤ9ĤmˤĤƤϡme (mod n)=mפȤʤ롣

p=2p'+1p'ǿˡפȤǿ٤СμΥåˤ٤ǰʬ򥢥르ꥺФƤ⶯ƥȽҤ٤Ƥ롣

ʿʸϰϤ¤Ƥȼ

[̿]
e=3mN1/3ΤȤŹʸʿʸޤ롣

[]

0cN줬

m3C (mod N)ע͡m3=cסʹƱˤʤä

ʤʤСc-m3=qNȤ롣

ǡ0cNˤ0m3Nʲˤꡢ

Nc-m3N椬äƤʤȤա
NqNN
1q1
q=0ʢq
c=m3

ϡNewtonˡʤɤȤäơc3躬Сm狼롣

RSAŹΥå

顼ؿΥץ

N=pqӦ(N)顢NǰʬǤ롣ԤϴΡԤ̤ΤǤ롣

(N)
=(pq)
=(p-1)(q-1)
=pq-(p+q)+1
=N-(p+q)+1

p+q=N+1-(N)

ȷδطꡢ
x2-(p+q)x+pq=0
x2-(N-(p+q)+1)x+N=0

򤱤p,qޤ롣

椨p,q줾ͤ狼ȤȤϡNǰʬ򤬤ǤȤ̣롣

[]Ȥä̾ͤ롣ñɽˡѤäǡäƤ뤳ȤܼŪƱǤ롣

ΥпΥץ

ɥС꡼Ne顢ľd׻륢르ꥺͰƤȤ롣

ed1 (mod (N))

(N,e,d)狼С(N)ܿΤ뤳ȤǤƤޤ

Źʸ

[̿]
RSAŹѤƤ륢ꥹΰŹʸcޥ꡼ʥɥС꡼ȤƯˤϤäȤ롣ΤȤޥ꡼ϥꥹˡ֤ʿʸyפʸ˽̾뤳Ȥǡcɤ뤳ȤǤ롣

[]

ꥹθ{e,N}̩dȤ롣ΤȤåŪcʿʸm=cdˤ򸫤Ĥ뤳ȤǤ롣

ޤå{e,N}ΤäƤΤǡǤդμrʡNˡʤ(r,N)=1ˤ֡

ơ3Ĥοx,y,t׻롣

xre (mod N)
yxc (mod N)
tr-1 (mod N)

{e,d}ϥꥹθ̩顢Ωġ

rxd (mod N)

ʤʤС(r,N)=1̩dꡢdϵʤΩ롣

ǡåϥꥹy˽̾뤳Ȥơuyd (mod N)פ롣

äơåtuФ褤

tu
=r-1yd
=r-1xdcd
=cdʢr-1xd=1
m (mod N)ʢd̤ΤμΩġ

椨ˡcʿʸǤmΤ뤳ȤǤ롣

ˡ

RSAŹˤNѤƤȤΤ褦ʥåͤ롣

[̿]
RSAŹѤƤ륢ꥹȥܥ֤ˡNѤƤơꥹθ{e1,N}ܥ֤θ{e2,N}ǡe1,e2ߤǤǤȤꥹȥܥ֤줾θǰŹ沽Ʊʿʸϡ2ĤΰŹʸȤȥꥹȥܥ֤θΤߤȤäǤ롣

[]

Ʊʿʸm򡢤줾쥢ꥹθ{e1,N}ܥ֤θ{e2,N}ǰŹ沽롣

c_{1}~\equiv~m^{e_{1}}~\,~\(mod~\,~N\)
c_{2}~\equiv~m^{e_{2}}~\,~\(mod~\,~N\)

e1,e2ϸߤǤ顢re1+se2=1פȤʤ(r,s)¸ߤ롣

ǡr0ȲꤷƤ褤ΤȤse2=1+(-r)e1ˤʤ롣

{c_{2}}^s~=~m^{se_{2}}~\equiv~m\(m^{-r}\)^{e_{1}}~\equiv~{mc_{1}}^{-r}~\,~\(~mod~\,~N\)

{c_{2}}^s{c_{1}}^{r}~\equiv~m~\,~\(~mod~\,~N\)

椨ˡʿʸmɤǤ롣

RSAŹ˴Ϣ̿

MathematicaȤ礭ʿͤRSAŹͤƤߤ

p,q礭ǿǤȤN=pqǰʬ򤬤ɤΤ餤񤷤ɤȤ߹ߴؿFactorIntegerǷ׻η׻֤ǸƤߤ롣

FactorIntegerؿ102ĤǿѤäǰʬǤޤ202ĤǿѤǰʬ򤹤Τ˿ɴääƤޤǤϡ1002ĤǿѤǰʬ򤵤褦Ȥȡ1,009áʡɴǯʾˤäƤޤޤ

1ޤǿpqɬפǤ롣

p=3664574846010398476366489053643765700783516938863189555441363547044071432448290328134024308367889052533548935668299012531156279317222051850414897
q=1168739572526100813876952673152034187217968575011849245168587228878827148719167713005832175236969768601794785141792640487056128411997957483261

2ĤǿNޤ

N
=p*q
=4282933639016094831817101683743193930536916585673149361384347302951329977289724840592100832851892684444299167366660190579341977611068564678602964534173494745937914174433037004679955855504781201342823643641524972444510058778292780466162694306965094083649652672349903177869165648782539117

2(N)׻롣mȤ롣

m
=(p-1)*(q-1)
=4282933639016094831817101683743193930536916585673149361384347302951329977289724840592100832851892684444299167366660190579341977611068564678599298790587911821360733808426720086944985120597342999938137111507252022184913049282445750325619568284662943353196211867178259842423531598974640960

mϼ¼ŪˣnpqǰʬǤʤе뤳ȤϤǤʤå¦MathematicaδؿFactorIntegerEulerPhiȤäƤ׻Ǥʤ

3mȸߤǤǤ2ʾm̤hӤ֡ϸʤΤǡΰդˤ狼ˤɬפϤʤޤ꾮ȰŹ沽θȤƤŬƤʤŬ˽ͤơͤ1䤷ʤGCD(h,m)=1ǤΤӽФ

ˡθk뤿ˡhx+my=1ExtendedGCDѤƵ롣ExtendedGCD[h,m]ͤ{GCD(h,m),{x,y}}ηͿ뤫顢ͤxʬʤ2ʬ1ʬmdzäȤ;kȤФ褤櫓

4ơǽäʿʸͤˤΤ򼡤AȤ롣

A=1234567890;

ŹʸBAhndzä;Ǥ뤬Ahͤ׻Ǥ륳ԥ塼¸ߤʤʤʤ顢ο2ʿɽȤɬפʷοŻҤοϤ뤫礭Ǥ롣

Mod[A^h,n]¹ԤƤ⡢褷֤äƤʤȤΤ褦ʷ׻ξPowerModѤнֻˤǤ롣

ʿʸľƤߤ롣ˤϤBͤkndzäޤФ褤Ǥ롣

ֻ˸οФƤ

5ǤϼºݤʸRSAŹǰŹ沽Ƥߤ롣RSAŹ礭ʿNǤˡѤΤǡ٤0N-1ȤϰϤο򰷤롣顢ʸİŹ沽ƤΤǤΨʤΤǡʸޤȤƤҤȤĤοͤѴ롣

ҤȤĤʸ026ޤǤΥ٥ɽƤΤǡsʸҤȤĤˤޤȤ뤳Ȥˤs27ʿȤߤʤȤǤ뤬027s-1ޤǤϰϤοˤʤ롣NˡȤΤɽˤϡ27sN¨slog27NǤʤФʤʤΤǡsͤϺ[log27N]Ȥʤ롣ǡ[x]xĶʤ¨ʬڤ겼ɽǤʥեؿˡ
ۤɷ᤿NˤĤ[log27N]׻ƤߤȼΤ褦ˤʤ롣

äơĹ199ʸޤǤϰĤοͤɽȤǤ櫓199ĶĹʸˤĤƤϡ199ʸȤ˶ڤäƳơͤľФ褤

6ǤϡʿʸHACKER_IS_NOT_CRACKERפȤơŹ沽Ƥߤ롣199ʸʲǤΤǡҤȤĤοͤǰŹ沽뤳ȤǤ롣

ʸ٥ľΤalphabettoLabels[s_String]fromLabels[l_List]Ƥ

alphabet = "_ABCDEFGHIJKLMNOPQRSTUVWXYZ"
toLabels[s_String]:=Map[(StringPosition[alphabet,#][[1,1]]-1)&,Characters[s]]
fromLabels[l_List]:=Apply[StringJoin,Map[StringTake[alphabet,{#+1}]&,]]

7ˤ27ʿɽȤߤʤͤľ

Ź渰Ȥäh褷Ndzä;롣

ŹʸȤˤϤοͤǤˤΤǡʸѴ롣Τˤ27ʿɽƷοͤ٥ȤʸѴ롣

ʾμ³ҤȤޤȤˤؿRSA[s,N,h]ȼΤ褦ˤʤ롣

RSA[str_String,N_,h_]:=fromLabels[IntegerDigits[PowerMod[FromDigits[toLabels[str],27],h,N],27]]

ȯԤϤʸŹʸȤ롣ȯԤϤʸۤɤƱ褦ˡʸ٥ľƤ27ʿȸʤƿͤľ渰k褷ΤNdzä;ᡢ27ʿɽγƷ٥ȤʸľȤˤʿʸ뤳ȤǤ롣μ³ۤɤΰŹ沽μ³ȤۤȤƱǡh褹ʬk褹뤳ȤѤäˤʤäơۤɺäؿRSAȤ椹뤳ȤǤ롣

RSAŹΰŹ沽ȤϻȤ㤦ǡ³ޤäƱͤǤȤȤפǤ롣˰Ź沽θhʣ粽θkȤhk1 (mod m)ȤطϤ2ĤθؤƤݤƤ롣äơθǰŹ沽Ź沽θ椹뤳Ȥǽʤ櫓ΤȤϡǥ̾ݤ˽פʥݥȤȤʤ롣

[]RSAŹθˡ2Ĥǿp,qʷ鸫ơ˶ᤤΤˤȤäƤϤʤʤ⤷ᤤȡn=p*qFactorInteger[N]ǿäǰʬ򤵤Ƥޤ
ʤʤС(p+q)/2=a(p-q)/2=bȤȡN=pq=(a+b)(a-b)=a2-b2ǡba٤˾Ȥ顢a=sqrt(N)Ȥʤꡢsqrt(N)⾯礭aǡa2-NʿǤ褦ʤΤ򸫤Ĥ뤳Ȥˤäơpqͤ뤫Ǥ롣

[]ʸn=3265956223274250684702820169ˡȤh=1234567Ź沽θȤRSAŹˤŹʸǤ롣
"AJXHABLSWBYNDVQKTYGG"
MathematicaȤäơɤ衣

[]

ɷ̡ʿʸϡTRTYAPDKEEQCTEGJCXFפȤ狼롣

RSAŹα

RSAŹѤƤ롣㤨м󤲤롣

  • TLSTransport Layer Security
  • IPSecIP Security

ʸ

  • ߥΡ
  • ظŹδÿ
  • ؾ꡼12Źȥǡƥ
  • ؿ޲򻨳ءŹ
  • إƥεѡ
  • إϥåɱкɥ֥å
  • ظŹδÿ
  • ʿ16ǯ١󥻥ƥɥߥ˥ȥ졼ʶܡ
  • Mathematicadzڤʳء