Base-256 Conversion in Public Key Encryption Systems

In this step of our AI Gomoku project, we'll explore public key encryption and decryption techniques, focusing on converting between decimal and base-256 number systems. Public key cryptography relies on the complexity of factoring large numbers, which ensures the algorithm's security when sufficiently large numbers are used.

The server uses the following public key:

• Exponent: 65537
• Modulus: 135261828916791946705313569652794581721330948863485438876915508683244111694485850733278569559191167660149469895899348939039437830613284874764820878002628686548956779897196112828969255650312573935871059275664474562666268163936821302832645284397530568872432109324825205567091066297960733513602409443790146687029

Before encrypting your password with this public key, we need to complete several verification steps:

1. Encrypt the number 31415926 using the public key and submit it as the 'num' field to http://2**.2**.**.1**:9012/step_05. If successful, proceed to the next step.
2. Convert the string 'hello, world!' to a number using the following rule: treat each character as a digit in base-256. For example:

'abc'
'a' = 97, 'b' = 98, 'c' = 99
'abc' = 97*256^2 + 98*256^1 + 99*256^0 = 6382179

Submit the converted number as the 'str2num' field to http://2**.2**.**.1**:9012/step_05. If successful, proceed to the next step.

3. Convert the string 'hello, world!' to a number, then encrypt it using the public key. Submit the encrypted number as the 'str' field to http://2**.2**.**.1**:9012/step_05. If successful, proceed to the next step.
4. Convert the string 'hello, world!' to a number, encrypt it using the public key, then convert the result to hexadecimal. Submit this hexadecimal value as the 'hex' field to http://2**.2**.**.1**:9012/step_05. If successful, proceed to the next step.

Now you can encrypt your actual password.

Task 5

Submit your username as the 'user' field and your encrypted password as the 'password' field to http://2**.2**.**.1**:9012/step_05.

To enhance security against potential eavesdroppers, we can add random padding to your password before encryption. Since the modulus in our public key is very large, we can encode substantial amounts of data. In C/C++, strings are terminated with a null character ('\0'), and any data after this character is ignored. We can append a null character followed by random data to our password before encryption. This ensures that each encryption produces a different ciphertext, providing better protection for your password.

The server also sends encrypted information that you'll need to decrypt. Since the server uses its private key to encrypt this data, you can use the public key to decrypt it.

Python Implementation

import requests as req

def fastModular(x):    # Fast modular exponentiation for encryption/decryption
    """x[0] = base"""
    """x[1] = exponent"""
    """x[2] = modulus"""
    result = 1
    while x[1] > 0:
        if x[1] & 1:
            result = (result * x[0]) % x[2]
        x[1] = x[1] >> 1    # Bitwise right shift is faster than division
        x[0] = (x[0] * x[0]) % x[2]
    return result

def str_to_num(strings):
    """Convert string to number using base-256 representation"""
    num_value = 0
    length = len(strings)
    for i in range(length):
        num_value += ord(strings[i]) * (256 ** (length - i - 1))
    return num_value

def num_to_str(num):
    """Convert number back to string using base-256 representation"""
    char_list = []
    while num != 0:
        char_list.append(num % 256)
        num = num // 256
    char_list.reverse()
    decoded_string = ''.join(chr(i) for i in char_list)
    return decoded_string

# Public key components
exponent = 65537
modulus = 135261828916791946705313569652794581721330948863485438876915508683244111694485850733278569559191167660149469895899348939039437830613284874764820878002628686548956779897196112828969255650312573935871059275664474562666268163936821302832645284397530568872432109324825205567091066297960733513602409443790146687029
password = 'XXXXX'  # Replace with actual password

# Encrypt password
encrypted_num = fastModular([str_to_num(password), exponent, modulus])
hex_encrypted = hex(encrypted_num)
print(f"Encrypted password (hex): {hex_encrypted}")

# Prepare request parameters
params = {
    'user': '1414081721',  # Replace with actual username
    'password': hex_encrypted
}

# Send request to server
response = req.get('http://2**.2**.**.1**:9012/step_05/', params=params)

# Process server response
if 'message' in response.():
    # Convert hex response to number
    encrypted_message = int('0x' + response.()['message'], 16)
    
    # Decrypt the message
    decrypted_num = fastModular([encrypted_message, exponent, modulus])
    
    # Convert number back to string
    decrypted_message = num_to_str(decrypted_num)
    print(f"Decrypted message: {decrypted_message}")

Troubleshooting Base Conversion

When implementing base-10 to base-256 conversion, you might encounter issues with integer division. In Python, using regular division (/) produces a float, while floor division (//) maintains integer values. This is crucial for correctly converting between number bases.

For example, when converting from base-256 back to a string, you need to use floor division (//) to extract each digit:

num = 6382179  # Example number
char_list = []
while num != 0:
    char_list.append(num % 256)
    num = num // 256  # Use floor division, not regular division

Using regular division instead of floor division can lead to incorrect results or infinite loops.

Public Key Cryptography and Key Exchange

Public key cryptography enables secure communication even when the communication channel is accessible to eavesdroppers. This is particularly important in network protocols like HTTP, where data is transmitted in plaintext.

The Diffie-Hellman key exchange algorithm, published by Martin Hellman and Whitfield Diffie in 1976, allows two parties to establish a shared secret over an insecure channel. Here's how it works:

1. Each party independently selects a private number.
2. Both parties agree on two public values: a base (primitive root) and a modulus (prime number).
3. Each party computes a public-private number (PPN) using the formula: PPN = base^private_number mod modulus.
4. Each party exchanges their PPN with the other party.
5. Each party computes the shared secret using the other party's PPN and their own private number: shared_secret = other_PPN^my_private_number mod modulus.

Both parties arrive at the same shared secret because:

(base^A mod modulus)^B mod modulus = (base^B mod modulus)^A mod modulus

This mathematical property ensures that both parties can compute the same shared secret without revealing their private numbers to each other or to eavesdroppers.

For this algorithm to work securely, the modulus must be a prime number, and the base must be a primitive root of that modulus. A primitive root is a number whose powers generate all possible residues modulo the prime number.