encryption (4 Part Series)

1 Encryption Part 1: Introduction to Encryption
2 Encryption Part 2: Diffie-Hellman & Public Key Cryptography
3 Encryption Part 3: RSA Encryption
4 Encryption Part 4: Hashes

RSA encryption

note: You can clone this repo and use it on your own machine.

RSA Encryption Overview

RSA was invented by NORAD in the early 1970’s but was deemed top secret. A few years later in 1977, Ron Rivest, Adi Shamir and Leonard Adleman independantly invented the exact same process for encryption and called it RSA. RSA is the most used software in the world to date and every internet user has used RSA at some point whether they knew it or not.

It shares many mathematical similarities with Diffie-Hellman encryption, but it’s conceptually a little different. Instead of thinking about public and private keys, RSA can be thought of as sending an unlocked padlock. It would be like someone who wants to receive a message sending an unlocked padlock to the sender who then locks his message and sends it back for decryption.

The problem RSA solves compared to Diffie-Hellman is that of key storage. When using Diffie-Hellman every key needs to be saved separately. This can be unwieldy for a large organizaion like a bank with many customers- the bank would need a different key for each customer. The solution to this is RSA! The bank can send the same lock, that they alone have keys for, out to many customers who can send encrypted messages back.

Common Uses of RSA encryption

Some common uses of RSA encryption are:

• The Signal protocol: An open source protocol for sending secure messages. Used by programs like Signal and WhatsApp. Though the signal protocol also uses a special version of Diffie-Hellman on top of RSA.
• HTTPS: The encrypted connection between a computer and a server from the World Wide Web uses SSL or TLS which is based on RSA.
• VPN: Like HTTPS, connecting to a VPN uses the SSL or TLS protocols.
• Encrypted File Systems: Many files and file systems are encrypted using RSA.

RSA Encryption Process

The entire process is based on Euler’s theorem: m φ ( n ) ≡ 1 m o d     n m^{φ(n)} \equiv 1 \mod n mφ(n)≡1modn , where φ ( n ) φ(n) φ(n) is the product of two large prime numbers.

Key Generation

1. Select Two Prime Numbers: Choose two large prime numbers, p and q.
2. Compute the Modulus n: Calculate n = p * q. The value of n is used as the modulus for both the public and private keys.
3. Calculate the Totient (phi φ φ φ ): Compute Euler’s totient function, φ(n) = (p-1) * (q-1).
4. Choose the Public Exponent e: Select an integer e such that 1 < e < φ(n) and e is coprime with φ(n). Often, e = 65537.
5. Determine the Private Exponent d: Calculate d as the modular multiplicative inverse of e modulo φ(n).

Encryption Process

1. Public Key: The public key consists of the modulus n and the public exponent e.
2. Encrypting a Message: Convert the message into an integer m (e.g., via ASCII). Then, compute the ciphertext c using c ≡ m e ( m o d n ) c ≡ m^e (mod n) c≡me(modn) .

Decryption Process

1. Private Key: The private key is made of the modulus n and the private exponent d.
2. Decrypting a Message: Decrypt the message by computing m ≡ c d ( m o d n ) m ≡ c^{d} (mod n) m≡cd(modn) using the private key.

Security

• RSA’s security relies on the difficulty of factoring the product of two large prime numbers.
• The security improves with larger key sizes but at the cost of slower encryption and decryption.

Let’s get coding: Helper Functions

These functions are meant for demonstration, not performance. This is just to show how the process of RSA, but this would never be used in production. In modern applications this process is completely automated.

<span># Finds factors and determines if prime. </span>
<span>def</span> <span>factors</span><span>(</span><span>number</span><span>):</span>
    <span>number</span> <span>=</span> <span>int</span><span>(</span><span>number</span><span>)</span>
    <span>factors</span> <span>=</span> <span>set</span><span>()</span>
    <span># Check for divisibility by 2 first to handle even numbers quickly </span>    <span>if</span> <span>number</span> <span>%</span> <span>2</span> <span>==</span> <span>0</span><span>:</span>
        <span>factors</span><span>.</span><span>update</span><span>({</span><span>2</span><span>,</span> <span>number</span> <span>//</span> <span>2</span><span>})</span>
    <span># Check for odd divisors only, up to the square root of the number </span>    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>3</span><span>,</span> <span>int</span><span>(</span><span>number</span><span>**</span><span>0.5</span><span>)</span> <span>+</span> <span>1</span><span>,</span> <span>2</span><span>):</span>
        <span>if</span> <span>number</span> <span>%</span> <span>i</span> <span>==</span> <span>0</span><span>:</span>
            <span>factors</span><span>.</span><span>update</span><span>({</span><span>i</span><span>,</span> <span>number</span> <span>//</span> <span>i</span><span>})</span>
    <span># Add 1 and the number itself to the factors </span>    <span>factors</span><span>.</span><span>update</span><span>({</span><span>1</span><span>,</span> <span>number</span><span>})</span>
    <span># A prime number has exactly two factors: 1 and itself </span>    <span>return</span> <span>{</span><span>'</span><span>factors</span><span>'</span><span>:</span> <span>factors</span><span>,</span> <span>'</span><span>is_prime</span><span>'</span><span>:</span> <span>len</span><span>(</span><span>factors</span><span>)</span> <span>==</span> <span>2</span><span>}</span>
<span># Determines greatest common divisor of 2 numbers </span>
<span>def</span> <span>gcd</span><span>(</span><span>a</span><span>,</span> <span>b</span><span>):</span>
    <span>while</span> <span>b</span><span>:</span>
        <span>a</span><span>,</span> <span>b</span> <span>=</span> <span>b</span><span>,</span> <span>a</span> <span>%</span> <span>b</span>
    <span>return</span> <span>a</span>
<span># encode a string into an array of each character's numerical value </span>
<span>def</span> <span>encode_string</span><span>(</span><span>string</span><span>):</span>
    <span>char_array</span> <span>=</span> <span>[]</span>
    <span>for</span> <span>char</span> <span>in</span> <span>string</span><span>:</span>
        <span>char_array</span><span>.</span><span>append</span><span>(</span><span>ord</span><span>(</span><span>char</span><span>))</span>
    <span>return</span> <span>char_array</span>
<span># decode an array of numerical values to their corresponding character </span>
<span>def</span> <span>decode_string</span><span>(</span><span>arr</span><span>):</span>
    <span>decoded_arr</span> <span>=</span> <span>[]</span>
    <span>for</span> <span>i</span> <span>in</span> <span>arr</span><span>:</span>
        <span>decoded_arr</span><span>.</span><span>append</span><span>(</span><span>chr</span><span>(</span><span>i</span><span>))</span>
    <span>return</span> <span>""</span><span>.</span><span>join</span><span>(</span><span>decoded_arr</span><span>)</span>
<span># Calculate if numbers are co-prime (they have no common factors except 1) </span>
<span>def</span> <span>are_coprime</span><span>(</span><span>number1</span><span>,</span> <span>number2</span><span>):</span>
    <span>number1_factors</span> <span>=</span> <span>factors</span><span>(</span><span>number1</span><span>)[</span><span>'</span><span>factors</span><span>'</span><span>]</span>
    <span>number2_factors</span> <span>=</span> <span>factors</span><span>(</span><span>number2</span><span>)[</span><span>'</span><span>factors</span><span>'</span><span>]</span>
    <span>common_factors</span> <span>=</span> <span>number1_factors</span><span>.</span><span>intersection</span><span>(</span><span>number2_factors</span><span>)</span>
    <span># if the intersection of common factors is only 1 return True </span>    <span>return</span> <span>common_factors</span> <span>==</span> <span>{</span><span>1</span><span>}</span>
<span># Finds factors and determines if prime. </span>
<span>def</span> <span>factors</span><span>(</span><span>number</span><span>):</span>
    <span>number</span> <span>=</span> <span>int</span><span>(</span><span>number</span><span>)</span>
    <span>factors</span> <span>=</span> <span>set</span><span>()</span>

    <span># Check for divisibility by 2 first to handle even numbers quickly </span>    <span>if</span> <span>number</span> <span>%</span> <span>2</span> <span>==</span> <span>0</span><span>:</span>
        <span>factors</span><span>.</span><span>update</span><span>({</span><span>2</span><span>,</span> <span>number</span> <span>//</span> <span>2</span><span>})</span>

    <span># Check for odd divisors only, up to the square root of the number </span>    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>3</span><span>,</span> <span>int</span><span>(</span><span>number</span><span>**</span><span>0.5</span><span>)</span> <span>+</span> <span>1</span><span>,</span> <span>2</span><span>):</span>
        <span>if</span> <span>number</span> <span>%</span> <span>i</span> <span>==</span> <span>0</span><span>:</span>
            <span>factors</span><span>.</span><span>update</span><span>({</span><span>i</span><span>,</span> <span>number</span> <span>//</span> <span>i</span><span>})</span>

    <span># Add 1 and the number itself to the factors </span>    <span>factors</span><span>.</span><span>update</span><span>({</span><span>1</span><span>,</span> <span>number</span><span>})</span>

    <span># A prime number has exactly two factors: 1 and itself </span>    <span>return</span> <span>{</span><span>'</span><span>factors</span><span>'</span><span>:</span> <span>factors</span><span>,</span> <span>'</span><span>is_prime</span><span>'</span><span>:</span> <span>len</span><span>(</span><span>factors</span><span>)</span> <span>==</span> <span>2</span><span>}</span>



<span># Determines greatest common divisor of 2 numbers </span>
<span>def</span> <span>gcd</span><span>(</span><span>a</span><span>,</span> <span>b</span><span>):</span>
    <span>while</span> <span>b</span><span>:</span>
        <span>a</span><span>,</span> <span>b</span> <span>=</span> <span>b</span><span>,</span> <span>a</span> <span>%</span> <span>b</span>
    <span>return</span> <span>a</span>



<span># encode a string into an array of each character's numerical value </span>
<span>def</span> <span>encode_string</span><span>(</span><span>string</span><span>):</span>
    <span>char_array</span> <span>=</span> <span>[]</span>
    <span>for</span> <span>char</span> <span>in</span> <span>string</span><span>:</span>
        <span>char_array</span><span>.</span><span>append</span><span>(</span><span>ord</span><span>(</span><span>char</span><span>))</span>
    <span>return</span> <span>char_array</span>



<span># decode an array of numerical values to their corresponding character </span>
<span>def</span> <span>decode_string</span><span>(</span><span>arr</span><span>):</span>
    <span>decoded_arr</span> <span>=</span> <span>[]</span>
    <span>for</span> <span>i</span> <span>in</span> <span>arr</span><span>:</span>
        <span>decoded_arr</span><span>.</span><span>append</span><span>(</span><span>chr</span><span>(</span><span>i</span><span>))</span>
    <span>return</span> <span>""</span><span>.</span><span>join</span><span>(</span><span>decoded_arr</span><span>)</span>



<span># Calculate if numbers are co-prime (they have no common factors except 1) </span>
<span>def</span> <span>are_coprime</span><span>(</span><span>number1</span><span>,</span> <span>number2</span><span>):</span>
    <span>number1_factors</span> <span>=</span> <span>factors</span><span>(</span><span>number1</span><span>)[</span><span>'</span><span>factors</span><span>'</span><span>]</span>
    <span>number2_factors</span> <span>=</span> <span>factors</span><span>(</span><span>number2</span><span>)[</span><span>'</span><span>factors</span><span>'</span><span>]</span>

    <span>common_factors</span> <span>=</span> <span>number1_factors</span><span>.</span><span>intersection</span><span>(</span><span>number2_factors</span><span>)</span>

    <span># if the intersection of common factors is only 1 return True </span>    <span>return</span> <span>common_factors</span> <span>==</span> <span>{</span><span>1</span><span>}</span>
# Finds factors and determines if prime. 
def factors(number):
    number = int(number)
    factors = set()

    # Check for divisibility by 2 first to handle even numbers quickly     if number % 2 == 0:
        factors.update({2, number // 2})

    # Check for odd divisors only, up to the square root of the number     for i in range(3, int(number**0.5) + 1, 2):
        if number % i == 0:
            factors.update({i, number // i})

    # Add 1 and the number itself to the factors     factors.update({1, number})

    # A prime number has exactly two factors: 1 and itself     return {'factors': factors, 'is_prime': len(factors) == 2}



# Determines greatest common divisor of 2 numbers 
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a



# encode a string into an array of each character's numerical value 
def encode_string(string):
    char_array = []
    for char in string:
        char_array.append(ord(char))
    return char_array



# decode an array of numerical values to their corresponding character 
def decode_string(arr):
    decoded_arr = []
    for i in arr:
        decoded_arr.append(chr(i))
    return "".join(decoded_arr)



# Calculate if numbers are co-prime (they have no common factors except 1) 
def are_coprime(number1, number2):
    number1_factors = factors(number1)['factors']
    number2_factors = factors(number2)['factors']

    common_factors = number1_factors.intersection(number2_factors)

    # if the intersection of common factors is only 1 return True     return common_factors == {1}

Enter fullscreen mode Exit fullscreen mode

Encryption Functions

Selecting the public key

e e e should be an integer that is not only greater than 1 but also less than φ ( n ) φ(n) φ(n) , where n = p q n = pq n=pq (the product of two distinct prime numbers p p p and q q q ).

e e e and φ ( n ) φ(n) φ(n) should be coprime, meaning they should have no common factors other than 1. This ensures that e e e has a multiplicative inverse m o d φ ( n ) mod φ(n) modφ(n) .

The private exponent d is the modular multiplicative inverse of e modulo ϕ(n).
This means d is the number that satisfies the equation
d × e ≡ 1   m o d ϕ ( n ) d × e ≡ 1 \ modϕ(n) d×e≡1 modϕ(n) .

<span># calulate phi (φ) - the totient </span>
<span>def</span> <span>calculate_phi</span><span>(</span><span>p</span><span>,</span> <span>q</span><span>):</span>
    <span>if</span> <span>factors</span><span>(</span><span>p</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]</span> <span>and</span> <span>factors</span><span>(</span><span>q</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]:</span>
        <span>return </span><span>(</span><span>p</span> <span>-</span> <span>1</span><span>)</span> <span>*</span> <span>(</span><span>q</span> <span>-</span> <span>1</span><span>)</span>
    <span>raise</span> <span>ValueError</span><span>(</span><span>'</span><span>Not prime numbers</span><span>'</span><span>)</span>
<span># Calculate e - the public exponent </span>
<span>def</span> <span>find_suitable_e</span><span>(</span><span>totient</span><span>):</span>
    <span># Start with 65537 - A common value for `e` in RSA </span>    <span>e</span> <span>=</span> <span>65537</span>
    <span># Check if e is less than totient and coprime with the totient </span>    <span># If not, decrement by 2 (to keep e as an odd number) and check again </span>    <span>while</span> <span>e</span> <span>>=</span> <span>totient</span> <span>or</span> <span>not</span> <span>are_coprime</span><span>(</span><span>e</span><span>,</span> <span>totient</span><span>):</span>
        <span>e</span> <span>-=</span> <span>2</span>
        <span>if</span> <span>e</span> <span><=</span> <span>2</span><span>:</span>
            <span>raise</span> <span>ValueError</span><span>(</span><span>"</span><span>Could not find an appropriate </span><span>'</span><span>e</span><span>'</span><span> value.</span><span>"</span><span>)</span>
    <span>return</span> <span>e</span>
<span># Encrypts each letter of the message with the exponent and modulus </span><span>def</span> <span>encrypt</span><span>(</span><span>message</span><span>,</span> <span>e</span><span>,</span> <span>n</span><span>):</span>
    <span>if</span> <span>isinstance</span><span>(</span><span>message</span><span>,</span> <span>list</span><span>):</span>
        <span>encrypted_list</span> <span>=</span> <span>[]</span>
        <span>for</span> <span>i</span> <span>in</span> <span>message</span><span>:</span>
            <span>encrypted_list</span><span>.</span><span>append</span><span>(</span><span>pow</span><span>(</span><span>i</span><span>,</span> <span>e</span><span>,</span> <span>n</span><span>))</span>
        <span>return</span> <span>encrypted_list</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>[]</span>
<span># Decrypts each letter of the message given d - the private key - and n - the modulus </span>
<span>def</span> <span>decrypt</span><span>(</span><span>message</span><span>,</span> <span>d</span><span>,</span> <span>n</span><span>):</span>
    <span>decrypted</span> <span>=</span> <span>[]</span>
    <span>for</span> <span>i</span> <span>in</span> <span>message</span><span>:</span>
        <span>decrypted</span><span>.</span><span>append</span><span>(</span><span>pow</span><span>(</span><span>i</span><span>,</span> <span>d</span><span>,</span> <span>n</span><span>))</span>
    <span>return</span> <span>decrypted</span>
<span># Calculate d: the private key </span><span>def</span> <span>calculate_d</span><span>(</span><span>phi_n</span><span>,</span> <span>e</span><span>):</span>
    <span>return</span> <span>pow</span><span>(</span><span>e</span><span>,</span> <span>-</span><span>1</span><span>,</span> <span>phi_n</span><span>)</span>
<span># calulate phi (φ) - the totient </span>
<span>def</span> <span>calculate_phi</span><span>(</span><span>p</span><span>,</span> <span>q</span><span>):</span>
    <span>if</span> <span>factors</span><span>(</span><span>p</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]</span> <span>and</span> <span>factors</span><span>(</span><span>q</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]:</span>
        <span>return </span><span>(</span><span>p</span> <span>-</span> <span>1</span><span>)</span> <span>*</span> <span>(</span><span>q</span> <span>-</span> <span>1</span><span>)</span>

    <span>raise</span> <span>ValueError</span><span>(</span><span>'</span><span>Not prime numbers</span><span>'</span><span>)</span>



<span># Calculate e - the public exponent </span>
<span>def</span> <span>find_suitable_e</span><span>(</span><span>totient</span><span>):</span>
    <span># Start with 65537 - A common value for `e` in RSA </span>    <span>e</span> <span>=</span> <span>65537</span>

    <span># Check if e is less than totient and coprime with the totient </span>    <span># If not, decrement by 2 (to keep e as an odd number) and check again </span>    <span>while</span> <span>e</span> <span>>=</span> <span>totient</span> <span>or</span> <span>not</span> <span>are_coprime</span><span>(</span><span>e</span><span>,</span> <span>totient</span><span>):</span>
        <span>e</span> <span>-=</span> <span>2</span>
        <span>if</span> <span>e</span> <span><=</span> <span>2</span><span>:</span>
            <span>raise</span> <span>ValueError</span><span>(</span><span>"</span><span>Could not find an appropriate </span><span>'</span><span>e</span><span>'</span><span> value.</span><span>"</span><span>)</span>

    <span>return</span> <span>e</span>


<span># Encrypts each letter of the message with the exponent and modulus </span><span>def</span> <span>encrypt</span><span>(</span><span>message</span><span>,</span> <span>e</span><span>,</span> <span>n</span><span>):</span>
    <span>if</span> <span>isinstance</span><span>(</span><span>message</span><span>,</span> <span>list</span><span>):</span>
        <span>encrypted_list</span> <span>=</span> <span>[]</span>
        <span>for</span> <span>i</span> <span>in</span> <span>message</span><span>:</span>
            <span>encrypted_list</span><span>.</span><span>append</span><span>(</span><span>pow</span><span>(</span><span>i</span><span>,</span> <span>e</span><span>,</span> <span>n</span><span>))</span>
        <span>return</span> <span>encrypted_list</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>[]</span>



<span># Decrypts each letter of the message given d - the private key - and n - the modulus </span>
<span>def</span> <span>decrypt</span><span>(</span><span>message</span><span>,</span> <span>d</span><span>,</span> <span>n</span><span>):</span>
    <span>decrypted</span> <span>=</span> <span>[]</span>
    <span>for</span> <span>i</span> <span>in</span> <span>message</span><span>:</span>
        <span>decrypted</span><span>.</span><span>append</span><span>(</span><span>pow</span><span>(</span><span>i</span><span>,</span> <span>d</span><span>,</span> <span>n</span><span>))</span>

    <span>return</span> <span>decrypted</span>



<span># Calculate d: the private key </span><span>def</span> <span>calculate_d</span><span>(</span><span>phi_n</span><span>,</span> <span>e</span><span>):</span>
    <span>return</span> <span>pow</span><span>(</span><span>e</span><span>,</span> <span>-</span><span>1</span><span>,</span> <span>phi_n</span><span>)</span>
# calulate phi (φ) - the totient 
def calculate_phi(p, q):
    if factors(p)['is_prime'] and factors(q)['is_prime']:
        return (p - 1) * (q - 1)

    raise ValueError('Not prime numbers')



# Calculate e - the public exponent 
def find_suitable_e(totient):
    # Start with 65537 - A common value for `e` in RSA     e = 65537

    # Check if e is less than totient and coprime with the totient     # If not, decrement by 2 (to keep e as an odd number) and check again     while e >= totient or not are_coprime(e, totient):
        e -= 2
        if e <= 2:
            raise ValueError("Could not find an appropriate 'e' value.")

    return e


# Encrypts each letter of the message with the exponent and modulus def encrypt(message, e, n):
    if isinstance(message, list):
        encrypted_list = []
        for i in message:
            encrypted_list.append(pow(i, e, n))
        return encrypted_list
    else:
        return []



# Decrypts each letter of the message given d - the private key - and n - the modulus 
def decrypt(message, d, n):
    decrypted = []
    for i in message:
        decrypted.append(pow(i, d, n))

    return decrypted



# Calculate d: the private key def calculate_d(phi_n, e):
    return pow(e, -1, phi_n)

Enter fullscreen mode Exit fullscreen mode

Watch RSA in action

<span># Alice picks 2 prime numbers of similar size to compute `n` </span>
<span>while</span> <span>True</span><span>:</span>
    <span>p1</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>(</span><span>'</span><span>Pick your first prime: </span><span>'</span><span>))</span>
    <span>p2</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>(</span><span>'</span><span>Pick your second prime: </span><span>'</span><span>))</span>
    <span>p1_is_prime</span> <span>=</span> <span>factors</span><span>(</span><span>p1</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]</span>
    <span>p2_is_prime</span> <span>=</span> <span>factors</span><span>(</span><span>p2</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]</span>
    <span>if</span> <span>p1_is_prime</span> <span>and</span> <span>p2_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>"</span><span>\n</span><span>Alice</span><span>'</span><span>s primes are </span><span>{</span><span>p1</span><span>}</span><span> and </span><span>{</span><span>p2</span><span>}</span><span>"</span><span>)</span>
        <span>break</span>
    <span>elif</span> <span>not</span> <span>p1_is_prime</span> <span>and</span> <span>not</span> <span>p2_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>'</span><span>{</span><span>p1</span><span>}</span><span> and </span><span>{</span><span>p2</span><span>}</span><span> are both not prime</span><span>'</span><span>)</span>
    <span>elif</span> <span>not</span> <span>p1_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>'</span><span>{</span><span>p1</span><span>}</span><span> is not prime.</span><span>'</span><span>)</span>
    <span>elif</span> <span>not</span> <span>p2_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>'</span><span>{</span><span>p2</span><span>}</span><span> is not prime.</span><span>'</span><span>)</span>
<span># Calculate n as the product of p1 and p2 </span>
<span>n</span> <span>=</span> <span>p1</span> <span>*</span> <span>p2</span>
<span>print</span><span>(</span><span>f</span><span>"</span><span>Alice</span><span>'</span><span>s n value is </span><span>{</span><span>p1</span><span>}</span><span> x </span><span>{</span><span>p2</span><span>}</span><span> = </span><span>{</span><span>n</span><span>}</span><span>"</span><span>)</span>
<span># Calculate the totient - φ(n) </span>
<span>totient</span> <span>=</span> <span>calculate_phi</span><span>(</span><span>p1</span><span>,</span> <span>p2</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>'</span><span>φ(n) = (</span><span>{</span><span>p1</span><span>}</span><span> - 1) x (</span><span>{</span><span>p2</span><span>}</span><span> - 1) = </span><span>{</span><span>totient</span><span>}</span><span>'</span><span>)</span>
<span># Calculate exponent e, such that it is odd and coprime with φ(n) </span>
<span>e</span> <span>=</span> <span>exponent</span><span>(</span><span>totient</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>'</span><span>The exponent value is </span><span>{</span><span>e</span><span>}</span><span>'</span><span>)</span>
<span># Calculate the private key `d`. Alice keeps this as her secret key. </span>
<span>d</span> <span>=</span> <span>calculate_d</span><span>(</span><span>totient</span><span>,</span> <span>e</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>"</span><span>Alice</span><span>'</span><span>s private decryption key is </span><span>{</span><span>d</span><span>}</span><span>"</span><span>)</span>
<span># Alice picks 2 prime numbers of similar size to compute `n` </span>
<span>while</span> <span>True</span><span>:</span>
    <span>p1</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>(</span><span>'</span><span>Pick your first prime: </span><span>'</span><span>))</span>
    <span>p2</span> <span>=</span> <span>int</span><span>(</span><span>input</span><span>(</span><span>'</span><span>Pick your second prime: </span><span>'</span><span>))</span>

    <span>p1_is_prime</span> <span>=</span> <span>factors</span><span>(</span><span>p1</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]</span>
    <span>p2_is_prime</span> <span>=</span> <span>factors</span><span>(</span><span>p2</span><span>)[</span><span>'</span><span>is_prime</span><span>'</span><span>]</span>

    <span>if</span> <span>p1_is_prime</span> <span>and</span> <span>p2_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>"</span><span>\n</span><span>Alice</span><span>'</span><span>s primes are </span><span>{</span><span>p1</span><span>}</span><span> and </span><span>{</span><span>p2</span><span>}</span><span>"</span><span>)</span>
        <span>break</span>
    <span>elif</span> <span>not</span> <span>p1_is_prime</span> <span>and</span> <span>not</span> <span>p2_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>'</span><span>{</span><span>p1</span><span>}</span><span> and </span><span>{</span><span>p2</span><span>}</span><span> are both not prime</span><span>'</span><span>)</span>
    <span>elif</span> <span>not</span> <span>p1_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>'</span><span>{</span><span>p1</span><span>}</span><span> is not prime.</span><span>'</span><span>)</span>
    <span>elif</span> <span>not</span> <span>p2_is_prime</span><span>:</span>
        <span>print</span><span>(</span><span>f</span><span>'</span><span>{</span><span>p2</span><span>}</span><span> is not prime.</span><span>'</span><span>)</span>



<span># Calculate n as the product of p1 and p2 </span>
<span>n</span> <span>=</span> <span>p1</span> <span>*</span> <span>p2</span>

<span>print</span><span>(</span><span>f</span><span>"</span><span>Alice</span><span>'</span><span>s n value is </span><span>{</span><span>p1</span><span>}</span><span> x </span><span>{</span><span>p2</span><span>}</span><span> = </span><span>{</span><span>n</span><span>}</span><span>"</span><span>)</span>



<span># Calculate the totient - φ(n) </span>
<span>totient</span> <span>=</span> <span>calculate_phi</span><span>(</span><span>p1</span><span>,</span> <span>p2</span><span>)</span>

<span>print</span><span>(</span><span>f</span><span>'</span><span>φ(n) = (</span><span>{</span><span>p1</span><span>}</span><span> - 1) x (</span><span>{</span><span>p2</span><span>}</span><span> - 1) = </span><span>{</span><span>totient</span><span>}</span><span>'</span><span>)</span>



<span># Calculate exponent e, such that it is odd and coprime with φ(n) </span>
<span>e</span> <span>=</span> <span>exponent</span><span>(</span><span>totient</span><span>)</span>

<span>print</span><span>(</span><span>f</span><span>'</span><span>The exponent value is </span><span>{</span><span>e</span><span>}</span><span>'</span><span>)</span>



<span># Calculate the private key `d`. Alice keeps this as her secret key. </span>
<span>d</span> <span>=</span> <span>calculate_d</span><span>(</span><span>totient</span><span>,</span> <span>e</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>"</span><span>Alice</span><span>'</span><span>s private decryption key is </span><span>{</span><span>d</span><span>}</span><span>"</span><span>)</span>
# Alice picks 2 prime numbers of similar size to compute `n` 
while True:
    p1 = int(input('Pick your first prime: '))
    p2 = int(input('Pick your second prime: '))

    p1_is_prime = factors(p1)['is_prime']
    p2_is_prime = factors(p2)['is_prime']

    if p1_is_prime and p2_is_prime:
        print(f"\nAlice's primes are {p1} and {p2}")
        break
    elif not p1_is_prime and not p2_is_prime:
        print(f'{p1} and {p2} are both not prime')
    elif not p1_is_prime:
        print(f'{p1} is not prime.')
    elif not p2_is_prime:
        print(f'{p2} is not prime.')



# Calculate n as the product of p1 and p2 
n = p1 * p2

print(f"Alice's n value is {p1} x {p2} = {n}")



# Calculate the totient - φ(n) 
totient = calculate_phi(p1, p2)

print(f'φ(n) = ({p1} - 1) x ({p2} - 1) = {totient}')



# Calculate exponent e, such that it is odd and coprime with φ(n) 
e = exponent(totient)

print(f'The exponent value is {e}')



# Calculate the private key `d`. Alice keeps this as her secret key. 
d = calculate_d(totient, e)
print(f"Alice's private decryption key is {d}")

Enter fullscreen mode Exit fullscreen mode

Alice sends n and e. Bob uses these numbers to encrypt

Alice sends to Bob her values for n and e. This is like sending an open lock that Bob will use to lock up his message. He does this by calculating m e m o d ( n ) m^{e} mod(n) memod(n) . Where m is the numerical value of his message.

<span># Bob's message to Alice </span><span>message</span> <span>=</span> <span>input</span><span>(</span><span>'</span><span>Type a message to send: </span><span>'</span><span>)</span>
<span>encoded_message</span> <span>=</span> <span>encode_string</span><span>(</span><span>message</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>'</span><span>Encoded but not encrypted message is:</span><span>\n</span><span>{</span><span>encoded_message</span><span>}</span><span>\n</span><span>'</span><span>)</span>
<span>encrypted_message</span> <span>=</span> <span>encrypt</span><span>(</span><span>encoded_message</span><span>,</span> <span>e</span><span>,</span> <span>n</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>'</span><span>Encoded and encrypted message is:</span><span>\n</span><span> </span><span>{</span><span>encrypted_message</span><span>}</span><span>'</span><span>)</span>
<span># Bob's message to Alice </span><span>message</span> <span>=</span> <span>input</span><span>(</span><span>'</span><span>Type a message to send: </span><span>'</span><span>)</span>

<span>encoded_message</span> <span>=</span> <span>encode_string</span><span>(</span><span>message</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>'</span><span>Encoded but not encrypted message is:</span><span>\n</span><span>{</span><span>encoded_message</span><span>}</span><span>\n</span><span>'</span><span>)</span>

<span>encrypted_message</span> <span>=</span> <span>encrypt</span><span>(</span><span>encoded_message</span><span>,</span> <span>e</span><span>,</span> <span>n</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>'</span><span>Encoded and encrypted message is:</span><span>\n</span><span> </span><span>{</span><span>encrypted_message</span><span>}</span><span>'</span><span>)</span>
# Bob's message to Alice message = input('Type a message to send: ')

encoded_message = encode_string(message)
print(f'Encoded but not encrypted message is:\n{encoded_message}\n')

encrypted_message = encrypt(encoded_message, e, n)
print(f'Encoded and encrypted message is:\n {encrypted_message}')

Enter fullscreen mode Exit fullscreen mode

Send the encrypted message

encrypted_message can now be sent from Bob to Alice without an eavesdropper (Eve) making any sense of the message. In practice this only works when large values of p and q are used, otherwise computers can still quite easily brute force the encryption.

Alice uses her private key d to decrypt the message

Since d is the multiplicative inverse of e in respect to φ(n), decrypting the message is easy. Each letter is decrypted with the function i d m o d ( n ) i^{d} mod (n) idmod(n) , where i is the encrypted numerical value of the letter, d is our private key, and n is the product of our two primes.

<span># Alice decrypts the message using `d` </span>
<span>decrypted_message</span> <span>=</span> <span>decrypt</span><span>(</span><span>encrypted_message</span><span>,</span> <span>d</span><span>,</span> <span>n</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>"</span><span>The decrypted encoded message is the same as above</span><span>\n</span><span>{</span><span>encoded_message</span><span>}</span><span> = </span><span>{</span><span>decrypted_message</span><span>}</span><span>\n</span><span>"</span><span>)</span>
<span>decoded_message</span> <span>=</span> <span>decode_string</span><span>(</span><span>decrypted_message</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>"</span><span>The plain text value is: </span><span>{</span><span>decoded_message</span><span>}</span><span>"</span><span>)</span>
<span># Alice decrypts the message using `d` </span>
<span>decrypted_message</span> <span>=</span> <span>decrypt</span><span>(</span><span>encrypted_message</span><span>,</span> <span>d</span><span>,</span> <span>n</span><span>)</span>

<span>print</span><span>(</span><span>f</span><span>"</span><span>The decrypted encoded message is the same as above</span><span>\n</span><span>{</span><span>encoded_message</span><span>}</span><span> = </span><span>{</span><span>decrypted_message</span><span>}</span><span>\n</span><span>"</span><span>)</span>


<span>decoded_message</span> <span>=</span> <span>decode_string</span><span>(</span><span>decrypted_message</span><span>)</span>
<span>print</span><span>(</span><span>f</span><span>"</span><span>The plain text value is: </span><span>{</span><span>decoded_message</span><span>}</span><span>"</span><span>)</span>
# Alice decrypts the message using `d` 
decrypted_message = decrypt(encrypted_message, d, n)

print(f"The decrypted encoded message is the same as above\n{encoded_message} = {decrypted_message}\n")


decoded_message = decode_string(decrypted_message)
print(f"The plain text value is: {decoded_message}")

Enter fullscreen mode Exit fullscreen mode

Next topic to tackle: Hashing

encryption (4 Part Series)

1 Encryption Part 1: Introduction to Encryption
2 Encryption Part 2: Diffie-Hellman & Public Key Cryptography
3 Encryption Part 3: RSA Encryption
4 Encryption Part 4: Hashes

原文链接：Encryption Part 3: RSA Encryption