LCS35
LCS35 är en kryptografisk utmaning och ett pussel som sattes av Ron Rivest 1999. Utmaningen är att beräkna värdet
där t är ett 14-siffrigt (eller 47-bitars) heltal, nämligen 79685186856218, och n är ett 616-siffrigt (eller 2048-bitars) heltal som är produkten av två stora primtal (som inte är givna). Värdet på w kan sedan användas för att dekryptera chiffertexten z , ett annat 616-siffrigt heltal. Klartexten ger den dolda informationen om faktoriseringen av n , vilket gör att lösningen lätt kan verifieras.
Tanken bakom utmaningen är att det enda kända sättet att hitta värdet på w utan att känna till faktoriseringen av n är genom t successiva kvadreringar. Värdet på t valdes för att få denna brute force-beräkning att ta cirka 35 år med 1999 års chiphastigheter som utgångspunkt och med hänsyn till Moores lag . Rivest noterar att "precis som ett misslyckande av Moores lag skulle kunna göra pusslet svårare än avsett, skulle ett genombrott inom factoringkonsten göra pusslet lättare än tänkt."
Utmaningen sattes vid (och har fått sitt namn från) 35-årsjubileumsfirandet av MIT Laboratory for Computer Science, nu en del av MIT Computer Science and Artificial Intelligence Laboratory .
LCS35-utmaningen löstes den 15 april 2019, tjugo år senare, av programmeraren Bernard Fabrot. Själva texten var ett "!!! Grattis på födelsedagen LCS !!!" meddelande.
Den 14 maj 2019 publicerade Ronald L. Rivest en ny version av LCS35 (som heter CSAIL2019) för att förlänga pusslet till år 2034.
externa länkar
- Beskrivning av LCS35 Time Capsule Crypto-pussel , Ronald L. Rivest
- Tidskapselöppningsceremoni