RSA encryption, private and public key calculation

RSA is a cryptosystem and used in secure data transmission. It is based on the difficulty of factoring the product of two large prime numbers.

If we already have calculated the private ”d” and the public key ”e” and a public modulus ”n”, we can jump forward to encrypting and decrypting messages (if you haven’t calculated them, please scroll downfurther this blog post).
Encryption
To encrypt a message one needs a public key ”e” and ”n”, which we take a look on how to calculate further, and a message ”m”.

Equation for encrypting the message
m^e mod n = c
”c” is the ciphertext, an result of encryption using cypher algorithm, such as the encryption algorithm demonstrated.

Decryption
To decrypt the message, one needs the ciphertext created ”c”, the public modulus ”n” and the own private key.

Equation to decrypt the message
c^d mod n = m
The equation results in message which was previously encrypted.

Example
Let’s assume that we have successfully generated the numbers e, d and n. If Alice would want to send Jack a message, she would need to know Jacks public key, which can be publicly available.
Alice is sending a message to Jack m = 42
(m is integer representation of the actual message, could be anything like ”hello world”. How the conversion is done, is up to other algorithm)
Jacks public key consist of number e = 17 and n = 3233.
Alice uses the encryption equation to encrypt the message:
m^e mod n = c
42^17 mod 3233 = 2557

Now Alice has the message encrypted with Jacks public key.
Alice send the ”c”, ciphertext to Jack.

Jack receives the message. He has private key ”d” = 2753. He uses it and public key component n to decrypt the message:
c^d mod n = m
2557^2753 mod 3233 = 42

Jack has successfully decrypted the message 42!

How to choose the e, d, n???
Here is the step by step explanation on how to calculate the private and the public key components.

1. Choose two very large prime numbers which are distinct from one another. Calculate the RSA modulus by multiplying them.
– For demonstration purposes I am going to use small numbers. Why to choose large prime numbers is explained pretty well in this stack overflow answer.

Our primes: p = 11, q = 5
RSA Modulus: n = 11*5 = 55

2. Calculate the phi φ (Euler’s totient function)
Euler’s totient function:
φ(n) = (p-1)(q-1)
φ(n) = (11-1) * (5-1) = 10*4 = 40

3. Select, e, that is relatively prime to the φ and is 1 < e < φ
A prime is relatively prime to some number, if they do not have any common divisor expect for 1. For checking that a number is relative to your φ, you can use Euclidean algorithm or just use your brains (:D I know. check this out http://easymathsteps.jimdo.com/number-system/relatively-prime-number/).
For number 40, our phi φ, relative primes can be 3, 5, 7, 9…
Select one of the relative primes, e. I am going to pick e = 7.

4. Find the inverse of e with respect of φ. That way we can find d.
The equation can be put out like this:
e*d mod φ(n) = 1
We need to solve d:
d is going to be solved by using the extended Euclidean algorithm.
For the love of mathematics in WordPress editor and because of the laziness, I am not going to explain the extended Euclidean algorithm here, please refer this video.
By calculating like in the video, we come to conclusion that the magic number d = 23.

5. To find out if our equation works (e*d mod φ(n) = 1)
we can use the calculated numbers to test it out:
e = 7, d = 23, φ(n)=40
7*23 mod 40 = 1 <-- IT WORKS :)

Private and Public key
After calculating e, d and n, we have successfully calculated the public and private key components.
Private key: d = 23 (your private information!), n = 55 (RSA public modulus) .
Public key: e = 7, n = 55

These posts are done in a purpose of being my personal notes for Information Security course exam. Might contain some inaccurate information.

Sources and check these out:
– Aalto materials
– Euclidean Algorithm
– The extended Euclidean algorithm
– How the RSA algorithm works, including how to select d, e, n, p, q, and φ (phi)
– Paper and Pencil RSA (starring the extended Euclidean algorithm)
– Relatively prime numbers

Access control matrix and list

Simple exam question in information security could be writing a access control matrix.
Access control matrix is the most simplest Access control representation model. It is useful abstraction, but not very useful beyond that.

Very common exam question could be demonstrating file/folder permissions of users and groups in a access control matrix.

Example output of an ls -l command in terminal:

-rw-r----- pekka guard 123123 10 Jan 20:23 inmates.txt
-rw----r-- teppo inmate 1213 11 Dec 20:23 diary.txt
-rw-rw-r-- jukka guard 20328 09 Feb 11:00 announcements.txt

With this kind of a terminal output the Access control matrix would look like:

	pekka	teppo	jukka
inmates.txt	read, write	–	read
diary.txt	read	read, write	read
announcements.txt	read, write	read	read, write

Access control list (ACL)

The same matrix representation of permissions could be turned into a access control list. Simply put, access control list contains list of object access rights.

By using the same terminal data as above lets make a access control list. The access control lists can be displayed in various format, as long as it is displayed as a list.

• inmates.txt:
• pekka: read, write
• teppo: –
• jukka: read
• diary.txt:
• pekka: read
• teppo: read, write
• jukka: read
• announcements.txt:
• pekka: read, write
• teppo: read
• jukka: read, write

These posts are done in a purpose of being my personal notes for Information Security course exam. Might contain some inaccurate information.

How to check and read your file permissions

Check your permission
For seeing what permissions the file contains, type to the terminal:

    $ ls -l the_file
    $ -rw-r--r-- 1 Iiro GroupName  123234 Nov 3 13:56 the_file

From here we see that owner of ”the_file” is Iiro,
the user has read and write permissions (-rw-r--r--),
”the_file” is owned by group ”GroupName”,
the group has read permission (-rw-r--r--),
Other users can read the file (-rw-r--r--).