Contest Material

---

The set of RSA public key is public (although contest is now closed).

Click here to Download Contest Material

The format for Contest Material is a text file. Each line represents a single public key and it contains three numbers written in decimal base and separated by a space: a counter identifying the public key (1,2,3,...), a modulus and a public exponent.

Warning for Windows users: If you open the file (i.e. in bloc notes) you might see all public keys on a single line. It should not be too difficult to process them manually or automatically to have each public key on a single line.

Read the Instructions below for further info.

Submission of Contest Solutions

---

A participant will be identified by a unique email address. A participant may submit one or more solutions to the contest at any time between the publication of Contest Material and the end of the context, which is set on Friday, 17th October at 17:00.

You submit a Contest Solution sending a mail to contest.cryptolabtn at gmail.com.

A submission may consists of one or more solution for a subset of the proposed RSA public keys. Multiple submissions are allowed but only the first three submission for each public key will be considered valid. Further submissions will be discarded. Format for submission is a text file. Each line will represent a contest solution for a single public key and it will contain four numbers written in decimal base and separated by a space: a counter identifying the public key (1,2,3,...), the two prime factors and the private exponent.

Coding

---

Do I have to code my own program to factorize an integer or find the private exponent? Short answer is: No, but Yes.

Long answer is: we have no way of checking if you have written your code to solve our contest (we are not asking to show the code and you can work in whichever programming language you prefer). And it will be probably be easier to look around for some already existing program which does all the work. But the whole point of this contest is to challenge yourself to understand a cryptographic problem, look out for possible solutions, write code that implements the solutions and try to make it more and more efficient.

Do I have to cook my own algorithms to factorize an integer or find the private exponent? Absolutely not!

There are tons of good algorithms which might break short or weak keys. Look around (did I already mention this?) and find an algorithm that you are able to understand. Then try to implement it. This already looks like a good strategy to have fun in the contest.

Instructions

---

Do you know what is RSA algorithm? If not, go learn something about it!

An RSA public key \((N,e)\) is given by two integers \(N\) (the modulus) and \(e\) (the public exponent). The modulus is the product of two prime integers \(p,q\): \[N=pq\] A message is represented as an integer \(m\) (plaintext) such that \(0 < m < N\). Encryption produces an integer \(c\) (ciphertext) through exponentiation by the public exponent modulo \(N\): \[c \equiv m^e \pmod N\]

The contest material is a set of RSA public keys. We will not give you encrypted messages to be decrypted.

The associated RSA private key \((N,d)\) is given by the modulus and an integer \(d\) (private exponent). The private exponent is linked to public exponent by the following relation: \[de \equiv 1 \pmod {(p-1)(q-1)}\] Decryption given a ciphertext \(c\) recovers the message \(m\) through exponentiation by the private exponent modulo \(N\): \[m \equiv c^d \pmod N\] The correctness of the algorithm can be proved by Euler's Theorem. Breaking an RSA public key means finding either \(d\) or factorize \(N\) into \(p\) and \(q\). Finding the factorization of the modulus or the private exponent is equivalent up to an efficient computation (see, for example here).

A contest solution for a single public key consists of both the prime factors of the modulus and the private exponent.

Final ranking

---

Rk	Partecipant	Time of Last Submission	Valid Keys
1	Lorenzo Felice Cameroni	00:55, 17/10/2014	45
2	CryptoBriscola*	15:10, 17/10/2014	45
3	CryptoBO**	11:17, 17/10/2014	44
4	Mauro Piva	11:50, 17/10/2014	44
5	Francesco Mantovani	12:20, 17/10/2014	44
6	Nanni Bassetti	10:33, 17/10/2014	43
7	Luca Chiodini	16:52, 17/10/2014	43
8	Alessandro Sebastian Podda	12:35, 14/10/2014	36
9	Cristiano Sgaravato	10:57, 17/10/2014	36
10	Luciano Giuseppe	15:05, 17/10/2014	36
11	Alessio Serraino	16:57, 17/10/2014	36
12	Matteo Rizzo	13:20, 17/10/2014	34
13	Flavio Santoro	16:59, 15/10/2014	33
14	John Johnson	20:29, 15/10/2014	33
15	Cristiano Regni	18:16, 15/10/2014	30
16	Amedeo Sgueglia	23:55, 15/10/2014	30
17	Luca Di Stefano	20:33, 15/10/2014	28

* group composed by Carlo Brunetta, Andrea Vinci, Jacopo di Bonito and Alessandro Melloni.

** group composed by Andrea Dari and Claudio Costa.

Ranking published only for participants with more than 20 valid keys.

Stats

---

Final stats (updated on Friday, 17th October, 17:00).

• Participants: 21
• Submissions: 52
• Submitted Keys: 677
• Valid Keys: 657
• Broken Keys: 46
• Unbroken Keys: 2

Identifier of unbroken keys: 37, 43.

Prizes

---

The real prize you get from participating in this contest is having fun learning and doing things by yourself. To give an additional incentive we have provided symbolic prizes for those who rank in the first three positions .

• The first of the ranking will receive a free annual subscription to Clusit, and the equivalent of 30€ in Bitcoin.
• The second of the ranking will receive the equivalent of 20€ in Bitcoin.
• The third of the ranking will receive the equivalent of 10€ in Bitcoin.

Prizes will be awarded on 22nd of December during an event organized at University of Trento.

Ranking

---

Ranking among participants is done considering the following two simple rules applying to all valid submissions.

1. A participant ranks higher than another participant if it has broken more public keys.

2. A participant ranks higher than another participant with the same number of broken public keys if his/her last valid submission for a broken public key was done earlier in time.

How did we design the contest?

---

We knew we wanted a contest where just using general purpose factorization algoritms would not be enough to excel in the competition. So we needed to generate weak keys. What are weak keys? These can be defined in an informal way as classes of keys where a special purpose algorithm exists, which perform better than best algorithm for modulus factorization.

First, we selected the class of weak keys we would want to generate. We chose:

• wiener weak keys: keys with small private exponent (\(d < \frac{1}{3}N^{1/4}\)) which can be broken with an implementation of Wiener's attack, based on continued fractions;
• fermat weak keys: keys where the modulus is the product of primes very near to each other (i.e. \( | p - q | < N^{1/4} \)), which can be broken easily with Fermat's factorization;
• pollard \(p-1\) weak keys: keys where the modulus has one prime factor \(p\) for which \(p-1\) is \(B\)-smooth for some low value of \(B\). These keys can be broken with Pollard's \(p-1\) attack.

To these three classes we added a couple of keys with a common prime factor, which can be broken very easily by computing Greates Common Divisors (these can be thought as randomness weak keys).

Next, we selected some key lengths (60,80,100,150,200,300,512,1024) and for each keylength, we generated 5 weak keys according to the above methods* and a sixth strong key, a key generated randomly without forcing any kind of previously known weakness. This process generated 48 keys which were ordered by keylength and generation method (strong key, common prime keys couple, wiener key, fermat key, pollard key).

*all our coding was done in the Magma language. Unfortunately, a bug in our implementation of the generation of pollard weak keys resulted in keys that, only for the longest keylengths, had a very small prime factor. We became aware of this only when the contest was already started.

Feedback from participants

---

We asked the participants the following questions:

• are you a student? high school or university?
• which city are you from?
• did you code some algorithm to participate? in which language? which algorithms did you code?
• did you use some existing tools? which ones?
• did you have access to a cluster or you just used personal desktops/laptops?
• did you learn something new on RSA?

We report here (with little editing) some of the answers from the participants. Sometimes these were in italian, and we left them that way. Note the curious twist in the challenge given by the use of a factorization database...

---

Nanni Bassetti (ranked 6th)

• are you a student? high school or university?

no, I'm a digital forensics expert and I'm 44 years old, I'm graduate in Computer Science at University of Bari.

• which city are you from?

Bari - Italy

• did you code some algorithm to participate? in which language? which algorithms did you code?

Yes, I coded a bash script and a python script they can factorize the module N and find the private exponent "d", but they are too slow.

• did you use some existing tools? which ones?

Yes, I used a combination of tools rsatool.py and the website: http://www.factordb.com/.

• did you have access to a cluster or you just used personal desktops/laptops?

I used my laptop and a website (http://www.factordb.com/)

• did you learn something new on RSA?

Yes, it was very formative.

---

Luca Chiodini (ranked 7th)

• are you a student? high school or university?

I'm a student, 5th year of high school.

• which city are you from?

I live in a small village near Bergamo.

• did you code some algorithm to participate? in which language? which algorithms did you code?

C++ (with boost::multiprecision to handle big numbers) and python have been used. Among other little things, I wrote a checker (given a ready-to-be-submitted output, it ascertained that RSA keys were valid).

• did you use some existing tools? which ones?

A lot! For instance:

• https://github.com/ius/rsatool,
• https://github.com/pablocelayes/rsa-wiener-attack,
• http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html
• did you have access to a cluster or you just used personal desktops/laptops?

I used my desktop (not a cluster, although quite powerful).

• did you learn something new on RSA?

I learned the algorithm right for this competition.

---

Luca Di Stefano (ranked 17th)

• are you a student? high school or university?
• which city are you from?

I'm a student from University of L'Aquila, currently attending the Laurea Magistrale course in Ingegneria Informatica e Automatica.

• did you code some algorithm to participate? in which language? which algorithms did you code?

I started by using a Python implementation of Wiener's attack I wrote some months ago. The code is available at https://github.com/lou1306/PythonRSA

• did you use some existing tools? which ones?

Then I brute-forced the first 24 keys by applying the MATLAB function factor() on their moduli. The function was useless for longer moduli because it was based on a simple sieve algorithm. I was going to implement a quadratic sieve but time ran out...

• did you have access to a cluster or you just used personal desktops/laptops?

I used my notebook for all computation.

• did you learn something new on RSA?

I already had a pretty good knowledge of RSA, but I definitely learned something on integer factorization and the quadratic sieve!

---

Luciano Giuseppe (ranked 10th)

• are you a student? high school or university?

I'm a university of Salerno master's student

• which city are you from?

I'm from Avellino province, Italy.

• did you code some algorithm to participate? in which language? which algorithms did you code?

No, I didn't

• did you use some existing tools? which ones?

I used yafu (http://sourceforge.net/projects/yafu/) for number under 90 digits, GGNFS and MSIEVE for others numbers as read here: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

• did you have access to a cluster or you just used personal desktops/laptops?

I used my desktop pc (pentium D, dual core)

---

CryptoBriscola (ranked 2nd)

Group composed by Carlo Brunetta, Andrea Vinci, Jacopo di Bonito and Alessandro Melloni.

• are you a student? high school or university?

Tutti della magistrale di Critto (NdR: all from MSc of Cryptography at University of Trento)

• which city are you from?

Misto Italia

• did you code some algorithm to participate? in which language? which algorithms did you code?

[...] siamo andati per la via più rapida. Magma, C++, Python. Alcuni eran già scritti, altri son stati adattati per il nostro scopo.

• did you use some existing tools? which ones?

Algoritmi pre-fatti per fattorizzare con algoritmi tipo GNFS

• did you have access to a cluster or you just used personal desktops/laptops?

Un portatile windows 8 per le prime chiavi piccole e quelle deboli ad attacchi particolari. (circa 29 chiavi) Un macbook pro per chiavi che sopra creavano problemi di memoria su windows. (circa 10 chiavi) Carta e penna per un attacco pigro facendo i gcd tra i vari n e così son uscite un paio di chiavi. (6 chiavi) Così siamo rimaste alle 3 che non abbiam potuto fare. In nottata abbiam fatto partire un piccolo server con qualche gpu e il GNFS Python che però non ha fruttato risultati. [...]

• did you learn something new on RSA?

Abbiamo testato un po' quel che abbiam visto a lezione!

---

Francesco Mantovani (ranked 5th)

• are you a student? high school or university?

Non sono uno studente, sono un web developer ma negli ultimi mesi ho lavorato in Corea come aiuto cuoco.

• which city are you from?

Seoul, Auckland (NdR: moved during the contest)

• did you code some algorithm to participate? in which language? which algorithms did you code?

Non ho scritto nemmeno una riga di codice, ho solo utilizzato python e perl per tradurre alcuni risultati che erano in esadecimale in decimale.

• did you use some existing tools? which ones?

mi sono imbattuto in questo post che spiega per filo e per segno come aprire una chiave RSA avendo questi dati. Mi sono quindi collegato a http://www.factordb.com/ e ho incominciato a trovare i numeri primi avendo solo i modulus. Trovati i numeri primi e stato poi facile grazie a rsatool https://github.com/ius/rsatool trovare "d". Non tutti i numeri però erano presenti nel DB. Il giorno seguente, avendo commesso alcuni errori, ho rivisto il lavoro e sono tornato a fare delle query sul database; mi sono accorto che alcuni dei numeri che il giorno prima non erano presenti nel db, il giorno seguente erano presenti. Forse, avendo ricevuto più richieste per quel dato numero, dall'altra parte si sono messi a cercare i numeri primi di quei moduli.

• did you learn something new on RSA?

Ho imparato qualcosa di nuovo? Un sacco di cose, soprattutto come funziona la vulnerabilità Heartbleed http://countuponsecurity.com/tag/extract-rsa-key/

---

Lorenzo Cameroni (ranked 1st)

• are you a student? high school or university?

I'm a 26 years old working student (well, honestly more working than student, I'm a full time java programmer and a Math student).

• which city are you from?

I work and study in Milano.

• did you code some algorithm to participate? in which language? which algorithms did you code?

Working full time leave me no much time for coding some smart algorithm, the only one I code is not so smart: a brute force search for a factor very close to the square root of n, but it was too slow for the key provided except first ones. I code this with PARI/GP. I didn't try to code Pollard's rho (which I think is the simpler serious factoring algorithm) because i knew that PARI/GP factor function already use this algorithm (hopefully better than how i could code in few hours).

• did you use some existing tools? which ones?

Yes, most of my work was finding the right tool for the right key, guessing what kind of "error" was done when the keys were created. Here the most useful I found:

• PARI/GP for general computations and for factoring "small" numbers (or big numbers with small factors) using the "factor" standard function.
• This browser java applet for Elliptic Curve Factorization (and for Self Initializing Quadratic Sieve) (I already knew the idea behind elliptic curve factoring but I didn't had enought time to study in detail the Quadratic Sieve). With this applet I factored some 90 digit numbers in roughly 4 hours each, although others (even larger) number were factored in few seconds.
• A modified version of this code for the Wiener attack. My modification allowed me to read input data in a different format.
• did you have access to a cluster or you just used personal desktops/laptops?

Only my laptop (and sometimes my work laptop)

• did you learn something new on RSA?

Of course: before this competition I never heard about attack on RSA such as Wiener's one, nor I could imagine that (as I read here) in real world different unrelated 1024 or 2048 bit RSA keys colud share a prime factor (altough this mostly happen when such keys are generated on embedded device with poor pseudo-random number generators)

---

CryptoBO (ranked 3rd)

Group composed by Andrea Dari and Claudio Costa.

• are you a student? high school or university?

Siamo 2 studenti universitari

• which city are you from?

Siamo di Bologna

• did you code some algorithm to participate? in which language? which algorithms did you code?

Abbiamo scritto vari algoritmi per fattorizzare il modulo, tra cui Fermat e Pollard rho oltre a quello a forza bruta. Sono stati scritti in Java ed utilizzando la programmazione multi-threaded.

NOTA AGGIUNTA NEL 2017
Andrea Dari ha pubblicato su GitHub la libreria creata in Java per il contest RSA awareness 2014, che poi ha utilizzato per fattorizzare molte delle chiavi pubbliche che venivano date. Link: https://github.com/cybernova/RSAbreaker
• did you use some existing tools? which ones?

Abbiamo utilizzato per alcune chiavi, quelle più semplici, WolframAlpha

• did you have access to a cluster or you just used personal desktops/laptops?

Abbiamo utilizzato i nostri laptop personali.

• did you learn something new on RSA?

Sicuramente abbiamo imparato che esistono algoritmi più o meno validi per cercare di fattorizzare un modulo anche abbastanza grande.

Fatto curioso: il mio amico che mi ha aiutato per il contest man mano che fattorizzavamo i moduli delle chiavi le pubblicava su factordb, chissà se qualcuno che si è piazzato prima di noi, ha cercato li dentro e ha trovato subito la soluzione...