Ett internationellt team av datavetare har satt ett nytt rekord för heltalsfaktorisering, ett av de viktigaste beräkningsproblemen som ligger till grund för säkerheten för nästan all kryptografi med offentliga nyckel som används idag.

Offentlig nyckelkryptering används för ett antal tillämpningar, inklusive kryptering av känsliga och konfidentiella data och digitala signaturer. I kryptografi med offentlig nyckel, nycklar som skyddar data kommer i par, en publik, och en privat. Säkerheten för krypteringen eller den digitala signaturen bygger på antagandet att det är omöjligt att beräkna den privata nyckeln från den offentliga nyckeln.

En av de vanligaste kryptografiska algoritmerna med offentlig nyckel för både kryptering och digitala signaturer är RSA-kryptosystemet, uppfanns 1977. Den är uppkallad efter sina uppfinnare Rivest, Shamir, och Adleman. Dess säkerhet bygger på det faktum att det anses vara svårt att faktorisera stora heltal av en specifik form.

För att uppmuntra forskning om heltalsfaktorisering, "RSA Factoring Challenges" skapades 1991. Dessa utmaningar bestod av utmaningsheltal av varierande storlek, namnges efter antalet heltalssiffror.

Teamet av datavetare från Frankrike och USA satte ett nytt rekord genom att faktorisera det största heltal i denna form hittills, den kryptografiska utmaningen RSA-250. Detta heltal är produkten av två primtal, var och en med 125 decimalsiffror. Totalt, det tog 2700 år att köra kraftfulla datorkärnor för att utföra beräkningen, vilket gjordes på tiotusentals maskiner runt om i världen under loppet av några månader.

Nyckeln som brutits med denna rekordberäkning är mindre än nycklar som vanligtvis skulle användas i praktiken av moderna kryptografiska applikationer:den har 829 binära bitar, där nuvarande praxis dikterar att RSA-nycklar bör vara minst 2048 binära bitar långa. Forskare använder dessa typer av beräkningar för att välja nyckelstyrkerekommendationer som kommer att förbli säkra under överskådlig framtid.

"Att uppnå beräkningsposter regelbundet är nödvändigt för att uppdatera kryptografiska säkerhetsparametrar och rekommendationer för nyckelstorlek, sa Nadia Heninger, professor i datavetenskap vid University of California San Diego, och en medlem av forskargruppen.

Samma team satte det tidigare heltalsfaktoreringsrekordet i december 2019, när de räknade in RSA-240-utmaningen, ett 795-bitars heltal.

Forskarna utförde denna beräkning med CADO-NFS, som är gratis programvara utvecklad av teamet på INRIA Nancy. De använde ett antal datorkluster, inklusive forskargrupp, universitet, och nationella forskningskluster i Frankrike, Tyskland, och UC San Diego.