Taggat med: faktorisering

ROCA: Ny attack mot RSA 1024 samt 2048-bitar

Uppdatering: Även smartcards från Gemalto med produktnamnet IDPrime.NET är sårbara för ROCA. Dock så säljer Gemalto ej dessa sedan September 2017. Gäller dock inte Gemalto-korten med snarlikt namn: Gemalto IDPrime MD.

RSA-nycklar som skapats med hårdvara från tillverkaren Infineon Technologies AG medger att en angripare kan genomföra faktoriseringsattacker. Och således återskapa den privata nyckeln från ett RSA-nyckelpar där enbart den publika RSA-nyckeln är känd. Attacken utnyttjar Coppersmith’s Attack där en låg exponent e används.

Kända användare av hårdvara från Infineon Technologies AG är bl.a. Estlands nationella ID-kort med smartcard.

The worst-case price of the factorization on an Amazon AWS c4 computation instance is $76 for the 1024-bit key and about $40,000 for the 2048-bit key.

Du kan testa om din publika RSA-nyckel är påverkad online eller offline:

Sårbarheten upptäcktes av slovakiska och tjeckiska säkerhetsforskare från Centrum för forskning om kryptografi och säkerhet vid Masaryk University, Tjeckien. Enigma Bridge Ltd, Cambridge, Storbritannien; och Ca ‘Foscari University of Venice, Italien.

Mer information nedan om CVE-2017-15361:

Källa: https://crocs.fi.muni.cz/public/papers/rsa_ccs17

Faktorisering av stora heltal

Om du är intresserad av faktorisering av stora heltal rekommenderar vi Johan Håstad nedan text från 2007.

Faktorisering av heltal är ett problem som fascinerat matematiskt intresserade människor i alla tider. Jakten på rekordstora primtal likaså. Om vi tar ett stort tal visar det sig vara mycket lättare att avgöra om det är primtal än att hitta faktorerna. Detta kan verka förvånande men det är faktiskt inte så underligt. Att vara primtal ger en mängd följdegenskaper och en användbar egenskap är Fermats lilla sats som säger att om p är primtal och a är ett tal mellan 1 och p − 1 så ger ap-1 rest 1 vid divsion med p.

Läs texten om faktorisering av stora heltal i sin helhet här via Forskning.se (pdf).

768-bitars RSA faktoriserat

Nu har RSA med 768-bitar faktoriserats av ett antal forskare.

Factorization of a 768-bit RSA modulus

Thorsten Kleinjung and Kazumaro Aoki and Jens Franke and Arjen Lenstra and Emmanuel Thomé and Joppe Bos and Pierrick Gaudry and Alexander Kruppa and Peter Montgomery and Dag Arne Osvik and Herman te Riele and Andrey Timofeev and Paul Zimmermann

Abstract: This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA.

Du hittar deras uppsats här:

http://eprint.iacr.org/2010/006

Intressant är följande citat:

Factoring a 1024-bit RSA modulus would be about a thousand times harder, and a 768-bit RSA modulus is several thousands times harder to factor than a 512-bit one.

Because the first factorization of a 512-bit RSA modulus was reported only a decade ago (cf. [7]) it is not unreasonable to expect that 1024-bit RSA moduli can be factored well within the next decade by an academic effort such as ours or the one in [7]. Thus, it would be prudent to phase out usage of 1024-bit RSA within the next three to four years.