Algorisme per servir com a estàndard de criptografia per a l’era de la computació quàntica


algoritme matemàtic

Crèdit: Unsplash/CC0 Public Domain

Els matemàtics sovint treballen en l’obscuritat, i això és probable perquè poques persones, a part dels companys matemàtics que comparteixen la mateixa subespecialitat, entenen el que fan. Fins i tot quan els algorismes tenen aplicacions pràctiques, com ajudar els conductors a veure els cotxes que s’acosten que l’ull no pot discernir, és el fabricant d’automòbils (o el seu desenvolupador de programari) qui obté el crèdit.

Això és especialment cert per als criptògrafs, els herois no reconeguts els algorismes dels quals mantenen les comunicacions i les dades de les persones segures quan utilitzen Internet, una tecnologia coneguda com a criptografia de clau pública.

Però de vegades, les matemàtiques pures afecten el món real. Això va passar aquest estiu quan l’Institut Nacional d’Estàndards i Tecnologies va seleccionar quatre algorismes de criptografia servir com a estàndards per a la seguretat de la clau pública en l’era imminent dels ordinadors quàntics, que farà que els sistemes de xifratge actuals quedin ràpidament obsolets.

Tres dels quatre algorismes escollits es basen en el treball dirigit per un equip de matemàtics de Brown: els professors Jeffrey Hoffstein, Joseph Silverman i Jill Pipher (que també exerceix de vicepresident d’investigació de Brown).

La història del NIST avalada Algorisme Falcon—i NTRU, el sistema criptogràfic de clau pública en què es basa Falcon— va començar a mitjans dels anys 90, quan informàtica quàntica encara estava en l’àmbit de la ciència ficció. En aquell moment, l’objectiu d’Hoffstein era desenvolupar un algorisme per simplificar i accelerar la manera com funcionaven els algorismes criptogràfics convencionals; el 1996, va cofundar NTRU Cryptosystems Inc. amb Silverman i Pipher (que també està casat amb Hoffstein) per portar-lo al mercat. Hoffstein va dir que la història de NTRU és una “saga sangrienta”, però finalment la companyia va tenir èxit, trobant un comprador adequat a Qualcomm. Falcon, que Hoffstein va dissenyar conjuntament amb nou criptògrafs més, i dos dels altres tres algorismes seleccionats pel NIST, es basen en el marc NTRU original.

Des d’abans del seu doctorat al MIT a través de cadascun dels càrrecs que ha ocupat a l’Institut d’Estudis Avançats de la Universitat de Cambridge, la Universitat de Rochester i Brown, Hoffstein ha estat “un tipus de números”, fins i tot: “Mai se m’ha passat pel cap. no ser matemàtic”, va dir. “Em vaig prometre que seguiria fent matemàtiques fins que ja no fos divertit. Malauradament, encara ho és!”

Després de la selecció del NIST, Hoffstein va descriure la seva transformació d’un teòric de nombres a un matemàtic aplicat amb una solució a un problema global imminent d’importància crítica.

P: Què és la criptografia de clau pública?

Quan us connecteu a Amazon per fer una compra, com sabeu que esteu realment connectat a Amazon i no un lloc web fals configurat per semblar exactament a Amazon? Aleshores, quan envieu la informació de la vostra targeta de crèdit, com l’envieu sense por que sigui interceptada i robada? La primera qüestió es resol amb el que es coneix com a signatura digital; el segon es resol mitjançant xifratge de clau pública. Dels algorismes estandarditzats del NIST, un és per a xifratge de clau pública i els altres tres, inclòs Falcon, són per a signatures digitals.

A l’arrel d’aquests es troben problemes de matemàtiques pures d’un tipus molt especial. Són difícils de resoldre (penseu: temps fins que s’acaba l’univers) si teniu una informació i són fàcils de resoldre (porten microsegons) si teniu una informació secreta addicional. El més meravellós és que només una de les parts que es comunica —Amazon, en aquest cas— necessita tenir la informació secreta.

P: Quin és el repte de seguretat que plantegen els ordinadors quàntics?

Sense un ordinador quàntic prou potent, el temps per resoldre el problema de xifratge és d’eons. Amb un ordinador quàntic potent, el temps per resoldre el problema es redueix a hores o menys. Per dir-ho de manera més alarmant, si algú tingués la possessió d’un ordinador quàntic fort, tota la seguretat d’Internet es trencaria completament. I l’Agència de Seguretat Nacional i grans corporacions aposten que d’aquí a cinc anys hi ha una bona probabilitat que es pugui construir un ordinador quàntic prou fort com per trencar Internet.

P: Heu creat la solució NTRU a principis i mitjans dels anys 90, molt abans que algú pensava en les necessitats de criptografia dels ordinadors quàntics potencials. Què pensaves en aquell moment?

Vaig trobar que els tres enfocaments principals de la criptografia de clau pública eren molt maldestres i poc estètics. Com a exemple, el mètode més conegut, RSA, consisteix a prendre nombres que tenen molts centenars de dígits, després augmentar-los a potències de centenars de dígits, dividint-los per un altre nombre que té centenars de dígits, i finalment agafant la resta. Aquest càlcul es pot fer fàcilment en un ordinador, però no és molt pràctic si teniu un processador petit i lleuger, com un telèfon mòbil del 1996. RSA també és molt lent, d’acord, mil·lisegons, però això encara compta com a lent.

El nostre somni era trobar un mètode per fer criptografia de clau pública que fos ordres de magnitud més ràpid que RSA i pogués funcionar en dispositius de poca potència. I ho vam fer! Les persones que el van implementar van poder fer-lo funcionar a velocitats de 200 a 300 vegades més ràpides que RSA. No ho vaig fer sol; vaig pensar obsessivament sobre el problema durant un any i mig, però no es va unir a una solució fins que em vaig unir amb Joe Silverman i Jill Pipher, els meus col·legues de Brown i els cofundadors de NTRU. .

P: Què significa NTRU?

Mai vam dir: la gent només va suposar que volíem dir quelcom tècnic i va fer servir la seva imaginació! Però significa “Number Theorists R Us”. Això va irritar la Jill, ja que és una analista harmònica, no una teòrica de nombres, però finalment em va perdonar.

P: Heu descrit la vostra empresa inicial NTRU Cryptosystems com a tenint unes cinc experiències “a prop de la mort”. Quins van ser alguns dels reptes que vau enfrontar?

Els guardians en el camp són majoritàriament criptògrafs que treballen per a empreses i en departaments d’informàtica. És increïblement difícil aconseguir que qualsevol algorisme nou es prengui seriosament, i és especialment difícil si no sou al club de criptografia. En el nostre cas, vam fer sonar les alarmes per dos motius. Per exemple, érem forasters i vam afegir una estructura addicional des de la teoria algebraica dels nombres fins a les gelosies per fer les coses més eficients.

Sempre que ho feu, hi ha un greu risc que hàgiu introduït debilitats accidentalment. Sí, és meravellós fer alguna cosa de manera més eficient. Però heu perdut alguna peça vital de seguretat en el procés? És completament comprensible que la gent desconfiï profundament d’aquesta estructura addicional, que va introduir la capacitat de multiplicar i sumar. Van passar 10 anys d’intens escrutini abans que la gent comencés a acceptar que no s’havia afegit cap debilitat.

P: Això no va ser només un exercici acadèmic. NTRU era una empresa que havia de treballar amb inversors i clients potencials. Al principi, NTRU va ser atacat injustament en un article escrit per alguns noms familiars en criptografia (que més tard van reconèixer el seu error). Com va sobreviure NTRU a això?

Va resultar que el seu document es va ignorar en gran mesura, però el nostre diari era prou interessant com per a que tothom s’hi endinsés. Van intentar atacar-lo i destruir-lo, i va rebre una gran quantitat d’atenció. Cada superfície que us podeu imaginar estava assetjada per ariets. La comunitat de criptografia era tan resistent a que els matemàtics envaïssin el seu territori. Si no haguéssim estat matemàtics coneguts de Brown, no hauríem sobreviscut a la polèmica. Al final, aquesta atenció probablement ens va ajudar.

P: Hi havia alguna manera en què ser matemàtics —fora, aquest món— fos un avantatge?

Del que estic més orgullós no és necessàriament el fet que l’algoritme en particular hagi acabat a les quatre finals de les eleccions NIST, tot i que cada un dels tres algorismes basats en gelosia utilitza la nostra estructura d’anell (la funció de multiplicació). Tots utilitzen les matemàtiques que vam introduir perquè després de més de 25 anys d’escrutini, no ha sorgit ni una debilitat per afegir aquesta estructura. Aquestes matemàtiques, que provenien de la teoria algebraica dels nombres, abans no formaven part de la criptografia. Forma part del que faig per a la meva altra vida, i em sembla especialment deliciós que hem pogut agafar aquesta cosa teòrica completament abstracta, aparentment inútil, i trobar una aplicació pràctica. Com a resultat, l’actual generació de criptògrafs ha de conèixer la teoria algebraica, que és una mica divertit.

P: Com és estar casat amb un altre matemàtic?

És la cosa més feliç de l’univers estar casat amb algú que entén el que és ser un matemàtic. En matemàtiques, el 99,9% del temps passes hores, setmanes, mesos i anys pensant en alguna cosa que no passa en res. Moltes vegades, penses que tens una idea fantàstica i no va enlloc. És meravellós estar casat amb algú que entén aquest sentiment, encara que no sempre entenem els detalls del que està treballant l’altre.

P: S’adona quan estàs perdut en els teus pensaments?

Sí, i probablement ella també.


El NIST anuncia els primers quatre algorismes criptogràfics resistents al quàntic


Proporcionat per
Universitat de Brown


Citació: Q&A: algorisme per servir com a estàndard de criptografia per a l’era de la computació quàntica (2022, 22 de setembre) recuperat el 23 de setembre de 2022 de https://phys.org/news/2022-09-qa-algorithm-cryptography-standard-quantum.html

Aquest document està subjecte a drets d’autor. A part de qualsevol tracte just amb finalitats d’estudi o investigació privats, no es pot reproduir cap part sense el permís per escrit. El contingut es proporciona només amb finalitats informatives.