Highlights



  • PhD Thesis

    Title: On the Cryptanalysis of Public-Key Cryptography
     
    Supervisor: Prof. Arjen K. Lenstra
    Obtained at the Laboratory for Cryptologic Algorithms (LACAL), École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland.
    [ PDF ] [ thesis website ]
     
    Abstract: Nowadays, the most popular public-key cryptosystems are based on either the integer factorization or the discrete logarithm problem. The feasibility of solving these mathematical problems in practice are studied and techniques are presented to speed-up the underlying arithmetic on parallel architectures.

    This thesis was nominated for the EPFL doctorate Award 2013 and received a special distinction from the selection committee.

  • Full abstract in English
    Nowadays, the most popular public-key cryptosystems are based on either the integer factorization or the discrete logarithm problem. The feasibility of solving these mathematical problems in practice are studied and techniques are presented to speed-up the underlying arithmetic on parallel architectures.

    The fastest known approach to solve the discrete logarithm problem in groups of elliptic curves over finite fields is the Pollard rho method. The negation map can be used to speed up this calculation by a factor $\sqrt{2}$. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. Furthermore, fast modular arithmetic is introduced which can take advantage of prime moduli of a special form using efficient "sloppy reduction." The effectiveness of these techniques is demonstrated by solving a 112-bit elliptic curve discrete logarithm problem using a cluster of PlayStation 3 game consoles: breaking a public-key standard and setting a new world record.

    The elliptic curve method (ECM) for integer factorization is the asymptotically fastest method to find relatively small factors of large integers. From a cryptanalytic point of view the performance of ECM gives information about secure parameter choices of some cryptographic protocols. We optimize ECM by proposing carry-free arithmetic modulo Mersenne numbers (numbers of the form $2^M-1$) especially suitable for parallel architectures. Our implementation of these techniques on a cluster of PlayStation 3 game consoles set a new record by finding a 241-bit prime factor of $2^{1181}-1$.

    A normal form for elliptic curves introduced by Edwards results in the fastest elliptic curve arithmetic in practice. Techniques to reduce the temporary storage and enhance the performance even further in the setting of ECM are presented. Our results enable one to run ECM efficiently on resource-constrained platforms such as graphics processing units.

  • Full abstract in French
    De nos jours, les cryptosystèmes à clef publique les plus populaires sont basés soit sur le problème de la factorisation des entiers, soit sur celui du logarithme discret. La faisabilité de la résolution pratique de ces problèmes mathématiques est étudiée, et des techniques pour l'accélération de l'arithmétique sous-jacente sur des architectures parallèles sont présentées.

    La plus rapide approche connue pour la résolution du problème du logarithme discret sur les groupes des courbes elliptiques sur corps finis est la méthode du Rho de Pollard. L'application de négation permet d'accélérer le calcul par un facteur $\sqrt{2}$. Il est communément reconnu que les marches aléatoires utilisées par le Rho de Pollard, en combinaison avec l'application de négation, s'égarent dans des cycles infructueux. Nous montrons que les approches précédentes pour éviter cette difficulté sont pénalisées par des cycles récurrents, et nous proposons des contre-mesures efficaces. De plus, nous introduisons une arithmétique modulaire rapide, qui tire avantage de modules premiers de forme spéciale, en utilisant l'efficace ``réduction hâtive''. Nous montrons l'efficacité de ces techniques en résolvant un problème de logarithme discret sur une courbe elliptique de 112 bits, sur un cluster de consoles de jeu PlayStation 3, cassant ainsi un standard de chiffrement à clef publique, et réalisant un nouveau record mondial.

    La méthode des courbes elliptiques (ECM) pour la factorisation des entiers est la méthode la plus rapide asymptotiquement pour identifier de relativement petits facteurs de grands entiers. D'un point de vue cryptanalytique, la performance d'ECM fournit des informations sur la sûreté du choix des paramètres de certains protocoles cryptographiques. Nous optimisons ECM en proposant une arithmétique modulo un nombre de Mersenne quelconque (nombres de la forme $2^M-1$) sans retenues, particulièrement adaptée aux architectures parallèles. Notre implémentation de ces techniques sur un cluster de consoles de jeu PlayStation~3 réalise un nouveau record en identifiant un facteur premier de 241 bits de $2^{1181}-1$.

    Une forme normale pour les courbes elliptiques, introduite par Edwards, donne en pratique l'arithmétique la plus rapide pour les courbes elliptiques. Nous présentons des techniques pour réduire le stockage temporaire et améliorer encore plus la performance dans le contexte d'ECM. Nos résultats permettent d'utiliser ECM efficacement sur des plateformes aux ressources limitées comme les GPU (processeurs graphiques).

  • Full abstract in German
    Die gebräuchlichsten Public-key Kryptosysteme beruhen heutzutage entweder auf dem Faktorisierungsproblem oder dem diskreten Logarithmus-Problem. In dieser Arbeit wird zum einen untersucht, inwieweit es möglich ist, diese mathematischen Probleme zu lösen, und zum anderen werden Techniken zur Beschleunigung der zugrundeliegenden Arithmetik auf parallelen Architekturen vorgestellt.

    Pollard's rho Verfahren ist der schnellste bekannte Ansatz, das diskrete Logarithmus-Problem in der Gruppe der Punkte einer elliptischen Kurve über einem endlichen Körper zu lösen. Dieses Verfahren kann mittels der Negationsabbildung um einen Faktor $\sqrt{2}$ beschleunigt werden. Bekanntlich können dabei die Zufallswege aus Pollard's rho Methode in fruchtlosen Zyklen enden. Wir zeigen, dass die bisherigen Ansätze, dieses Problem zu lösen, mit dem Problem der wiederkehrenden Zyklen zu kämpfen haben, und schlagen effektive Alternativen vor. Ausserdem stellen wir für Primmoduli einer speziellen Form eine schnelle modulare Arithmetik vor, die effiziente "saloppe Reduktion" benutzt. Mit der Lösung eines 112-Bit elliptischen diskreten Logarithmus-Problems auf einem Verbund von PlayStation 3 Spielkonsolen, was einen Public-key Standard bricht und einen neuen Weltrekord aufstellt, wird die Effektivität dieser Techniken unter Beweis gestellt.

    Die asymptotisch schnellste Methode, relativ kleine Faktoren grosser Zahlen zu finden, ist die elliptische Kurven Methode (ECM). Für die Kryptographie ist sie wichtig, um Informationen über sichere Parameter für einige kryptographische Protokolle zu erhalten. Wir haben ECM mit einer übertragsfreien Arithmetik optimiert, die für Arithmetik modulo Mersennezahlen (Zahlen der Form $2^M-1$) auf parallelen Architekturen besonders geeignet ist. Mit unserer Implementierung dieser Techniken haben wir auf einem Verbund von PlayStation 3 Spielkonsolen mit einem 241-Bit Primfaktor von $2^{1181}-1$ einen neuen Rekord aufgestellt.

    Eine von Edwards eingeführte Normalform für elliptischen Kurven führt zur schnellsten Arithmetik auf elliptische Kurven in der Praxis. Im Falle der Anwendung auf ECM stellen wir Techniken vor, die den temporären Speicherbedarf reduzieren und die Laufzeit noch weiter verbessern. Dies erlaubt uns, ECM auf ressourcenbeschränkten Plattformen wie Graphikprozessoren laufen zu lassen.

  • Full abstract in Italian
    Al giorno d'oggi, i sistemi crittografici a chiave pubblica più popolari, sono basati sul problema della fattorizzazione di numeri interi o su quello del logaritmo discreto. Verrà presentato lo studio relativo alla risoluzione di tali problemi matematici nella pratica e saranno presentate tecniche per accelerare l'aritmetica utilizzata su architetture parallele.

    L'approccio più veloce per risolvere il problema del logaritmo discreto in un un gruppo di punti su una curva ellittica è il metodo rho di Pollard. L'utilizzo della "mappa di negazione" può essere adottato per velocizzare l'elaborazione di un fattore $\sqrt{2}$. E' ben noto che le passeggiate aleatorie usate da Pollard, combinate con la mappa di negazione, possono entrare in cicli infruttuosi. Mostreremo che, gli approcci pubblicati precedentemente in letteratura per affrontare questo problema, sono affetti da cicli ricorrenti e proporremo contromisure alternative efficaci. Inoltre, verrà introdotta un'aritmetica modulare veloce, per moduli dalla forma speciale, basata su una tecnica di riduzione efficiente denominata "riduzione pigra". L'efficacia di tali tecniche è stata dimostrata risolvendo un'instanza del problema del logaritmo discreto su una curva ellittica a 112-bit usando un cluster di console PlayStation 3: uno standard crittografico a chiave pubblica è stato attaccato con successo ed un nuovo record mondiale è stato stabilito.

    Il metodo delle curve ellittiche (ECM) per la fattorizzazione di interi è asintoticamente il metodo più veloce per trovare fattori piccoli (relativamente) di interi molto grandi. Dal punto di vista della crittanalisi le prestazioni di ECM influiscono sulla scelta dei parametri di sicurezza di alcuni protocolli crittografici. Noi abbiamo ottimizzato ECM, proponendo un'aritmetica senza resti particolarmente adatta ad architetture parallele e moduli definiti da numeri di Mersenne: numeri della forma $2^M-1$. La nostra implementazione di queste tecniche, su un cluster di console PlayStation 3, ha stabilito un nuovo record: è stato trovato un fattore di 241-bit del numero $2^{1181}-1$.

    Una forma normale per le curve ellittiche introdotta da Edwards consente di lavorare, nella pratica, con l'aritmetica delle curve ellittiche più veloce in assoluto. Verrano presentate tecniche pratiche per ridurre l'occupazione di memoria e per migliorare le prestazioni di tale aritmetica. I nostri risultati consentono di eseguire ECM in maniera efficiente su piattaforme dalle risorse limitate come i processori grafici.

  • Full abstract in Dutch
    Tegenwoordig zijn de populairste asymmetrische cryptosystemen gebaseerd op het probleem van de ontbinding van een geheel samengesteld getal in priemfactoren of op het discrete logaritme probleem. De praktische mogelijkheden om deze wiskundige problemen op te lossen worden bestudeerd en technieken worden gepresenteerd om de berekeningen te versnellen op parallelle computerarchitecturen.

    De snelste manier om het discrete logaritme probleem in groepen van elliptische krommen over een eindig lichaam op te lossen is het Pollard rho algoritme. Spiegelbeelden kunnen worden gebruikt om de berekening met een factor $\sqrt{2}$ te versnellen, tenzij de toevalsbewegingen erdoor in nutteloze cycli terecht komen. We tonen aan dat eerder gepubliceerde methoden om dit probleem op te lossen door terugkerende cycli niet werken en we laten zien hoe ook dit probleem kan worden opgelost. Verder introduceren we "slordige reductie" om modulair rekenen met getallen van een speciale vorm te versnellen. We laten zien dat dit in de praktijk werkt door een 112-bit elliptische kromme asymmetrische standaard te kraken. De berekening werd gedaan op een cluster bestaande uit PlayStation 3 spelcomputers en zette een nieuw wereldrecord.

    De elliptische kromme methode (ECM) is de asymptotisch snelste methode om kleine priemfactoren te vinden. De grootte van de factoren die ermee gevonden kunnen worden geeft aan hoe de parameters van sommige cryptosystemen gekozen moeten worden. Voor toepassing van ECM op Mersenne getallen (getallen van de vorm $2^M-1$) hebben we een snelle overdrachtsvrije rekenmethode ontwikkeld die zeer geschikt is voor parallelle computerarchitecturen. Op het spelcomputercluster hebben we er een nieuw ECM record mee gevestigd door een 241-bit priemfactor te vinden van $2^{1181}-1$.

    Een paar jaar geleden heeft Edwards de tot nu toe snelste manier bedacht om met elliptische krommen te rekenen. We laten zien hoe de voor toepassing op ECM vereiste hoeveelheid geheugen drastisch kan worden verminderd. Dit maakt het mogelijk ECM te versnellen op architecturen met beperkt geheugen zoals grafische kernen (GPUs).