» »

Uspešna faktorizacija RSA-200 in RSA-640

Uspešna faktorizacija RSA-200 in RSA-640

Schneier.com - Kot poroča MathWorld news, je skupina nemških strokovnjakov na German Federal Agency for Information Technology Security uspešno faktorizirala 193-mestno število znano kot RSA-640 in ob tem pobrala nagrado v vrednosti 20.000 USD. Že pred tem (decembra 2003) pa je ista skupina uspela faktorizirati 200 mestno število (RSA-200).

Faktorizacija je poseben matematični postopek iskanja praštevilčnih faktorjev danega števila. Napadalec, ki bi mu uspelo izpeljati faktorizacijo RSA, bi lahko na podlagi tega postopka odkril zasebni ključ in tako dešifriral sporočilo.

Raziskovalci, ki so imeli pred seboj število "310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609" so morali ugotoviti iz katerih dveh faktorjev je to število sestavljeno. In rezultat? Število je zmnožek naslednjih dveh števil:

1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579
x
1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571

Če ne verjamete, lahko izračun preverite na roke...

17 komentarjev

gumby ::

kalkulator mi napako javi:D

edit: 3.10741660575e192 mi pa vrne cifro, ce uporabim realna stevila... kar precejsnja napaka nastane

Zgodovina sprememb…

  • spremenil: gumby ()

gzibret ::

PC je tuki kar švoh. Ne vem, če bi Mathlab premlel. Bo treba kar na roke preverit.
Vse je za neki dobr!

OwcA ::

Mathematica rabi manj kot sekundo (P-M 1,6 GHz).
Otroška radovednost - gonilo napredka.

tx-z ::

na roke??? kko da fak bi ti to zračunu brez kalkulatorja?? to bi rebu 15let:\
tx-z

gumby ::

15 let ne ravno, rabil bi pa dovolj velik list papirja:)

Matthai ::

Zelo dobro Owca. Zdaj pa poiskusi še v drugo smer. :D
All those moments will be lost in time, like tears in rain...
Time to die.

BigWhale ::

Jaz sem imel to stvar napisano na enem listku.... Eh.. pa je slo $20k

;>

GBX ::

> time echo "1634733645 8092538484 4313388386 5090859841 7836700330 9231218111 0852389333 1001045081 5121211816 7511579 * 1900871281 664822113 1268515739 3541397547 1896789968 5154936666 3853908802 7103802104 4989571912 61465571" | python -i
Python 2.4 (#1, Mar 22 2005, 21:42:42)
[GCC 3.3.5 20050117 (prerelease) (SUSE Linux)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 3107418240 4900437213 5075003588 8567930037 3460228427 2754572016 1948823206 4405180815 0455634682 9671723286 7824379162 7283803341 5471073108 5019195485 2900733772 4822783525 7423864540 1469173660 2477652346609L
>>>

real 0m0.515s
user 0m0.016s
sys 0m0.010s


~ malo popravil številke, ker so preveč raztegnile stran. v orginalu pisane brez presledkov ;) / Racer D

Zgodovina sprememb…

Romčy ::

Predvidevam da če nebi obstajal copy-paste, danes te novice nebi bilo tu. ;-)

BBB ::

Kako se tako velika cela števila običajno zapiše v spremenljivke v programskih jezikih? Se to naredi s serijo integer spremenljivk? Če je tako, kakšen je potem postopek množenja?

drola ::

Verjetno gre vse skupaj v string, potem pa podobno, kot se računa pisno.
https://drola.si

Gizmo_X ::

Ja, double kmalu izgubi na natančnosti.:\

Domača naloga za fanatike: v asemblerju napiši subrotino, ki zmnoži 1024 bitni števili.>:D :D
Don't pay the BILL at the big GATES.

BaRtMaN ::

Za vejitve verjetno še nisi slišal?

marjans ::

omača naloga za fanatike: v asemblerju napiši subrotino, ki zmnoži 1024 bitni števili.


V assemblerju je to relativno zelo enostavno. V binarnem svetu se množenje dveh števil pretvori v bitno shiftanje in seštevanje. Potrebno je toliko shiftanj kolikor bitno število množimo (v tem primeru 1024) in toliko seštevanj, kolikor je enic v množitelju. Obe operaciji pa sta (s stališča assemblerja) zelo enostavni in hitri. Seveda se nekaj dodatnega časa izgubi zaradi velikosti števil (žal so registri v današnjih procish nekoliko prekratki).

4DFX ::

Derive 6 potrebuje celih 0.000 sekunde :)
Verjetno gre seveda za zaokrožitev... še vedno pa to pomeni, da potrebuje manj kot 0.001 sekunde.

Pri faktoriziranju pa je druga zgodba... po 5 minutah se ni nič premaknilo, zato sem proces prekinil >:D
Očitno 3GHz procesor tudi približno ni dovolj za kaj takega... sploh pa so najbrž pri German Federal Agency for Information Technology Security uporabili kakšno zelo optimizirano metodo (članka nisem prebral :P)

LP,
4DFX

Zgodovina sprememb…

  • spremenil: 4DFX ()

JerKoJ ::

Ja drugic preber clank.
Za faktoriziranje so porabl cluster 80ih 2.2 GHz opteronov in je trajal skupi 4.5 mesce.
Tko da to da se teb v 5 minutah ni nc premaknil ni nc cudnga :)

Zgodovina sprememb…

  • spremenil: JerKoJ ()

CaqKa ::

>>> Očitno 3GHz procesor tudi približno ni dovolj za kaj takega...

ma nemoj :)

moj hp to naredi z levo roko


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

mnozenje matrik

Oddelek: Programiranje
194096 (3758) Vesoljc
»

Znanost in tehnologija VI.

Oddelek: Novice / Znanost in tehnologija
244177 (3324) whitto
»

Znanost in tehnologija V.

Oddelek: Novice / Znanost in tehnologija
143822 (3244) nicnevem
»

Prostovoljca rabim

Oddelek: Programiranje
141067 (823) Thomas
»

rekurzija - problem?

Oddelek: Programiranje
373244 (2808) Vesoljc

Več podobnih tem