RSA Factoring Challenge - RSA Factoring Challenge

RSA Factoring Challenge byla výzva předložila RSA Laboratories dne 18. března 1991 na podporu výzkumu výpočetní teorii čísel a na praktickou potíž factoring velká celá čísla a praskání RSA klíčů používaných v kryptografii . Publikovali seznam semiprimes (čísel s přesně dvěma hlavními faktory ) známých jako čísla RSA s peněžní cenou za úspěšnou faktorizaci některých z nich. Nejmenší z nich, 100místné číslo s názvem RSA-100 byla zapracována do 1. dubna 1991. Mnoho z větších čísel ještě nebylo započítáno a očekává se, že zůstanou nefaktorizované po nějakou dobu, avšak díky pokrokům v kvantových počítačích je tato předpověď nejistá kvůli Shorovu algoritmu .

V roce 2001 rozšířila společnost RSA Laboratories výzvu pro factoring a nabídla ceny v rozmezí od 10 000 do 200 000 $ za factoringová čísla od 576 bitů do 2048 bitů.

Výzvy pro faktoring RSA skončily v roce 2007. Laboratoře RSA uvedly: „Nyní, když průmysl má podstatně pokročilejší znalosti o kryptoanalytické síle běžných algoritmů symetrického klíče a veřejného klíče , tyto výzvy již nejsou aktivní.“ Když výzva skončila v roce 2007, byly z čísel výzev z roku 2001 započítány pouze RSA-576 a RSA-640.

Úkolem faktoringové výzvy bylo sledovat špičku v celočíselné faktorizaci. Primární použití je pro výběr délku klíče na RSA šifrování pomocí veřejného klíče schématu. Pokrok v této výzvě by měl poskytnout pohled na to, které klíčové velikosti jsou stále bezpečné a na jak dlouho. Jelikož RSA Laboratories je poskytovatelem produktů na bázi RSA, využili tuto výzvu jako pobídku pro akademickou komunitu k útoku na jádro jejich řešení - aby prokázali svou sílu.

Čísla RSA byla generována na počítači bez jakéhokoli síťového připojení. Pevný disk počítače byl následně zničen, takže by nikde neexistoval žádný záznam o řešení faktoringové výzvy.

První vygenerovaná čísla RSA, RSA-100 až RSA-500 a RSA-617, byla označena podle jejich počtu desetinných míst; další čísla RSA (počínaje RSA-576) byla vygenerována později a označena podle jejich počtu binárních číslic. Čísla v tabulce níže jsou uvedena v rostoucím pořadí i přes tento posun z desítkového na binární.

Matematika

RSA Laboratories uvádí, že: pro každé číslo RSA n existují prvočísla p a q taková

n = p × q .

Problém je najít tyto dvě prvočísla, daná pouze n .

Ceny a záznamy

Následující tabulka poskytuje přehled všech čísel RSA. Upozorňujeme, že výzva RSA Factoring Challenge skončila v roce 2007 a za factoring vyšších čísel nebudou uděleny žádné další ceny.

Čísla výzev v bílých čarách jsou čísla vyjádřená v základně 10 , zatímco čísla výzev ve žlutých čarách jsou čísla vyjádřená v základně 2

Viz také

• Čísla RSA , desetinná rozšíření čísel a známé faktorizace
• LCS35
• The Magic Words are Squeamish Ossifrage , řešení nalezené v roce 1993 pro další výzvu RSA položenou v roce 1977
• Výzva tajného klíče RSA
• Záznamy o faktorizaci celého čísla

Poznámky