# Practice 5 - Grid security and using grid to break RSA encryption

**Date**: 13.03.2012**Deadline**: 31.03.2012

## References

Referred documents and web sites contain supportive information for the practice.

**Grid Security**

- Presentation: "Security, Authorisation and Authentication"
- "Nice to meet you, authentically" at isgtw.org by Jens Jensen:

**Grid Policies**

- All Grid users have to know the Grid Acceptable Use Policy
- Other EGI SPG policies

**RSA**

- about RSA
- Generating RSA key
- Euclidean algorithm
- Extended Euclidean algorithm
- Coprime numbers
- Modular multiplicative inverse
- Eero Vainikko's presentation

## RSA protocol and its key generation algorithm

RSA is an algorithm for public-key cryptography that is based on the presumed difficulty of factoring large integers, the factoring problem. It is a block-algorithm: both message to be encrypted M and the encrypted message consist of blocks of length 0 to n-1. Each block is encrypted separately.

- Choose two distinct prime numbers p and q, p != q. Calculate n = pq, which will be the modulus for the RSA keys.
- Calculate f = (p-1)(q-1).
- Choose an integer e between 1 and f (1<e<f) such that e and f are coprime, meaning gcd(e,f) = 1.
- Two integers a and b are said to be coprime if they have no common positive divisor other than 1.
- For example, 14 and 15 are coprime, but 14 and 21 are not, because they are both divisible by 7.
- Simple way is to choose prime number as e and check that it does not divide f evenly

- Determine d, which is the multiplicative inverse of e (st. (d*e-1)mod f = 0)
- This is often computed using the
**extended Euclidean algorithm**.

- This is often computed using the

- n and e make up the public key
- n and d make up the private key
- To encrypt a message M: C = (M^e) mod n
- To decrypt a crypted message C: M = (C^d) mod n

### Exercise 5.1: Prime Factorization

Write a Python function that tests whether a given integer is a prime number. Its input parameter is n and it prints out the list A, whose members are prime factors of n: p(i), i = 1,..., k not decreasing order. (p(1) = 1).

The prime factors of a positive integer are the prime numbers that divide that integer exactly, without leaving a remainder.

Given a positive integer n>=2, the prime factorization is written

n=p(1)*p(2)*...*p(k)

where p(i) is a prime and k>0

For example:

- 64=1*2*(32)=1*2*2*(16)=1*2*2*2*(8)=1*2*2*2*2*(4)=1*2*2*2*2*2*2 => A=[1,2,2,2,2,2,2]
- 63=1*3*(21)=1*3*3*7 => A=[1,3,3,7]
- 31=1*31 => A=[1,31]

If you use a naive algorithm for finding the factors of a number n, you only have to check from

**3, 5, 7 to sqrt(n)** for possible factors and whatever is remaining is the last factor of the number.

More information about Prime Number Factorization is here.

### Exercise 5.2. Breaking a short RSA key

The goal of this exercise is to break RSA encryption by factorizing modulus (n) of the RSA public key. We use the factorizing algorithm from the first exercise (5.1) for this.

- Write a python script to break a public RSA key using integer factorization on n:
- n = 3397
- e = 25
- encrypted message = 2238 1912 1036 1741 1085 1741 1787 3246 2875 2303 953 3344 1741 1085 2284 1312 1821 2615 684 554 1119 596

- Implement:
- Breaking the RSA public key
- find p and q by factoring n: n = p*q.
- find d based on the RSA key generation algorithm

- Encrypting and decrypting messages
- use
**pow(number, power, module)**instead of pow(number, power) or the script will slow down a lot in the next exercise

- use
- Translating the integers into letters. Every number in the decrypted message represents up to two letters (a=01, b=02, c=03, ... , z=26, '_'=27)
- Don't forget to do the calculations in "mod n" (use special python power operator that takes modulus as one of the arguments)

- Breaking the RSA public key

### Exercise 5.3 Breaking a long RSA key using grid

- This time the modulus n is larger and thus takes much longer to break, divide the work into separate tasks and run them in the grid in parallel:
- n = 735496527042361698197
- e = 65537
- encrypted message = 554783151939784225220 329493461727553999721 478295784271965142497 524653331350380928112 294556639671273634819 348744886808846452213 98713214772161146219 605687051522992469211 324990868682581068485 77921517171776397465

- Your integer factorization must be minimally optimized! or it will run too long. (Do not check even divisors, only check until square root of n, etc.)

- Every number in the decrypted message represents up to 10 letters (a=01, b=02, c=03, ... , z=26, '_'=27)
- Divide the
**factoring**of n into at least 5 grid jobs (each has it's own xRSL file with different python script arguments), each job checking a different range for possible factors of n and run them all at the same time in the grid for parallelization. - Encrypting and decrypting can be done outside grid in a separate python script

#### Deliverables

- python scripts
- xRSL files
- Grid job result files (stdout) for each of the jobs
- Answers to both assignments (Decrypted message)
- How long did it take to run the grid jobs.
- Command line outputs that proves you have been running the exercises.

Also don't forget to read the Grid practical exercise solution format page to learn how to finalize and upload your solution.