RSA Algorithm

RSA is an Internet Encryption and Authentication System that uses an algorithm developed by Ron Rivest, Adi Shamir, and Leonard Adleman.

RSA Encryption is widely used and is one of the defacto Ecncryption standard.

It uses Modular Arithmetic and Elementary Number Theories to perform computations using two large prime numbers

RSA Algorithm Encryption

We let y = E(x) be the encryption function where x is an interger and y is the encrypted from of x

y = x^e mod n

RSA Algorithm Decryption

We let X = D(y) be the decryption function where y is an encryted integer and X is the decrypted from of y

X = y^d mod n

Example

1, We start by selecting primes p = 3 and q =11.

2. n = pq = 33

m = (p-1)(q-1) = (2)(10) = 20

3. Try e = 3

ged(3.20) = 1

=> e is co-prime to n

4. Find d such that 1= de mod m

=> 1 = Km + de

Using the extended Euclid Algorithm we see that 1 = -1 (20) + 7(3)

=> d = 7

5. Now let’s say that we want to encrypt the number x = 9:

We use the Encryption function y = x^e mod n

y = 9³ mod 33

y = 729 mod 33 = 3

=> y = 3

6. To decrypt y we use the function X =y^d mod n

X = 3⁷ mod 33

X = 2187 mod 33 = 9

=> X = 9 = x

=> It Works!

PassWord Cracking

Passwords aren’t generally stored in plaintext form. A file containing all the passwords in plain text form would be far too attractive a target, so instead, a one-way hash function is used. The best-known of these functions is based on DES and is called crypt.

— — — — — — — — — — — — — — — — — — -

Originally published at https://exploitbyte.com on November 3, 2019.