RSA Algorithm Explanation
Uploaded by
Kleopas KapalangaRSA Algorithm Explanation
Uploaded by
Kleopas KapalangaRSA algorithm from scratch with only python in built functions and some math.
Group D: Kleopas Shiikalepo Kapalanga 221000771
Shalom Vongayi Kuchekwa 224160826
Introduction
RSA algorithm is a public-key cryptography algorithm that enables secure key
exchange over insecure channels. It relies on the difficulty of factoring the
product of two large primes and on properties of modular arithmetic, particularly
the existence of a multiplicative inverse modulo.
Algorithm Description
Steps
1: Prime Numbers
Since RSA starts with two prime numbers.
Our own is an is_prime(n) function that checks divisibility up to the square root
of n. It’s not the fastest, but it works well especially for demonstration purpose.
We then use the gen function; gen_prime (bits), in order to generate a random prime
with a given number of bits (we opt to keep it simple and hence used 16-bit for
each prime, so the modulus is just around 32-bits).
2. Key Generation
We used the following function: make_keys (bits) to create the keys:
- Firstly the function pick two random primes p and q, it then compute n = p * q.
- Compute Euler’s totient phi = (p-1)(q-1).
- Choose a public exponent e (I start with 3 and increase until it’s coprime with
phi).
- Find the private exponent d using the modular inverse of e mod phi.
The result is (n, e) as the public key and (n, d) as the private key.
3. Encryption
To encrypt, we needed to convert the message into numbers. We foresee that the
modulus n might be smaller than the whole message, hence the message is split into
chunks that fit.
- The chunk size is (n.bit_length() - 1) // 8 bytes.
- Each chunk is converted from bytes to an integer, then encrypted with c = m^e mod
n.
- All ciphertext chunks are stored in a list.
This is done in the function encrypt(msg, n, e).
4. Decryption
To decrypt, we just needed to reversed the process:
- For each ciphertext block c, compute m = c^d mod n.
- Convert the integer back to bytes.
- Concatenate all the chunks and decode to a string.
This is done in the function decrypt(blocks, n, d).
5. Demonstration
Result:
We Kleopas and Shalom Making RSA keys for demo)...
Public: (49256897, 7)
Private: (49256897, 21098443)
Msg: hello rsa, this is Assignment 2 for Group D!
Cipher blocks: [46629040, 3495122, 42494167, 36811294, 3453994, 5596546, 14552812,
8255942, 25325417, 35515755, 28076359, 899696, 45023161, 16743349, 24078228]
Decrypted: hello rsa, this is Assignment 2 for Group D!
We tested the algorithm at the bottom of the code sheet:
A key pair with a 32-bit modulus was generated.
The keys were printed.
The message "Hello rsa, this is Assignment 2 for Group D!!" was encrypted.
The cipher text blocks were printed.
The message was verified to match when it was decrypted back to plaintext.
6. Notes:
To make it run quickly, we used small primes. Primes in actual RSA have to be
hundreds of bits long.
- In practice, this version is not completely secure because it lacks padding,
unlike OAEP.
- The primary objective was to illustrate RSA message chunking, encryption,
decryption, and key generation using python.
Strengths of RSA algorithm
Public-key architecture: there is no need to share a secret key beforehand thus
enables secure key distribution and digital signatures.
Versatility: supports confidentiality, authentication and non-repudiation via
digital signatures.
Strong theoretical basis: correctness relies on number-theoretic properties of
modular exponentiation and the chosen e, d pairings.
Weaknesses
Factoring vulnerability: RSA security hinges on the difficulty of factoring n thus
advances could compromise RSA in the future.
Computational cost: public-key operations are slow; typically used to protect small
data for example a session key rather than large messages.
Key size and security level: recommended key sizes may grow over time.
Conclusion
RSA provides robust public-key confidentiality and authentication when implemented
with appropriately large keys and proper padding. Strong key management secure
generation, storage, rotation, and revocation is important for long-term security.
