Miller-Rabin Python Implementation (slow but readable):
http://mchost/sourcecode/Miller-Rabin.py
As with my other subjects for week 2 I was absent for Adv. Network Security so this will be a summary of the lecture notes and reading materials. The title for this weeks lecture was ‘Adv. Cryptology, RSA and its implementation’. Considering the extensive assignment we completed last semester on PGP/GPG and it’s utilization of the RSA public key system, this will most likely be somewhat of a revision. I wrote a summary of the RSA system in that assignment which is will paraphrase below:
Generating Public and Private Keys (RSA):
Step 1: Generate two prime numbers
n = pq (let’s make p = 5 and q = 7)
5 * 7 = 35
n = 35
Step 2: Calculate the totient of n
φ(n) = (p – 1)(q – 1), φ is Euler's totient function
(5 - 1)(7 - 1)
φ(n) = 24
Step 3: Choose an integer, e, that is between 1 and φ(n) and co-prime with φ(n)
1 ,2 , 3 and 4 are not co-prime, however 5 is.
Let e = 5.
(e, n), (5, 35) is the public key.
Step 4: Using the public key and p*q (n), find the private key, d by finding the modular multiplicative inverse of e (mod(φ(n))
d = e^–1 mod φ(n)
d = 5^-1 mod φ(24)
Apply the Extended Euclidean algorithm (see http://mchost/sourcecode/eea.py)
d = 29
public key = (5, 35)
private key = (29, 35) The encryption process for RSA is as follows: plaintext message = m, public key = (e, n) m^e mod(n) = cypher-text The decryption process follows as: cypher-text message = c, private key = (d, n) c^d mod(n) = plaintext message Signing of documents can be done, ideally using a hash function, a private key and a trusted certificate for the public key: plaintext message = m, public key = (e, n), private key = (d, n)
hashFunction(m)^d mod(n) = signature
A recipient can confirm the signature with the following process: signature^e mod (n) = hashFunction(m)
The lecture notes explain these processes with much more correct mathematical notation, however this is the easiest way for me to express the process.
Also discussed in the lecture was a topic generating and tesing prime numbers. I did not complete strong analysis of ths process in the past semester. The Miller-Rabin test was introduced here. As per usual I find the easiest way to get my head around mathematical algorithms is not reviewing the mathematical proof/concept but by writing a script implementing the algorithm: http://mchost/sourcecode/Miller-Rabin.py