Encryption#

Data sent over the internet can potentially be read by “anyone”. This overview examines steps that can be taken to prevent information from getting into the wrong hands.

Warning: These are my “steps” to explore encryption. Don’t use the code in your projects - use standard libraries instead. Some of this may be outright wrong - check other sources to learn the fundamentals of encryption.

%connect pico

Connected to pico @ serial:///dev/ttyUSB1

Symmetric Key Encryption#

MicroPython has built-in support for the Advanced Encryption Standard (AES).

import ucryptolib, os

key = os.urandom(16)
print("key =", key[:20], "...")
msg = b'iot49 is awesome!'

# encrypt

enc = ucryptolib.aes(key, 1)
# pad msg to multiple of 16 bytes
padded = msg + b'\x00' * ((16 - (len(msg) % 16)) % 16)
encrypted = enc.encrypt(padded)
print("encrypted =", encrypted[:20], "...")

# decrypt

dec = ucryptolib.aes(key, 1)
decrypted = dec.decrypt(encrypted)
# decrypted message included padding, if any was added
print("decrypted =", decrypted[:20], "...")

# verify
assert decrypted[:len(msg)] == msg, "decrypted message differs!"

key = b'\x18\xee\x1f\xb3\xe7O\x9c\xc2\x03\xfc\xce[s\x97\x13c' ...
encrypted = b'\xf0D4zUO\xc9\x85\xe9yM\x19\xff_\xe2\xdd\x00\xb9\xbe\x01' ...
decrypted = b'iot49 is awesome!\x00\x00\x00' ...

This “works” - it would be difficult to “guess” the message from the encrypted data without knowing the key.

But how do we share the key between devices? We need encryption! What looks like a recursive problem has an elegant solution.

Public Key Cryptography#

Public Key Cryptography (PKC) uses two keys: a public key for encryption, and a private key for decryption.

To send me a secret message, you ask me for my public key. It’s public and hence can be transmitted without encryption. You use this public key to encrypt the message and send me the result. I recover the original, unencrypted message using my private key (that is never shared).

The public and private keys are generated from prime numbers. Here is a simple (and inefficient) function to generate (not so) large random prime numbers.

import random

from math import sqrt, log2

def is_prime(n):
    return n > 1 and all(n % i for i in range(2, int(sqrt(n)+1)))
    
def gen_prime(bits=32):
    p = 1
    while not is_prime(p):
        p = random.getrandbits(bits)
    return p

for i in range(5):
    p = gen_prime(bits=32)
    print("{:2}: {:30}  {:3} bits".format(i, p, int(log2(p))))

 0:                      439392509   28 bits
 1:                     3161980531   31 bits
 2:                     3662739161   31 bits
 3:                     2941471303   31 bits
 4:                     4239141733   31 bits

Now generate the keys:

def multinv(modulus, value):
    '''Multiplicative inverse in a given modulus

multinv(191, 138)
        18
18 * 138 % 191
        1
    '''
    # http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
    x, lastx = 0, 1
    a, b = modulus, value
    while b:
        a, q, b = b, a // b, a % b
        x, lastx = lastx - q * x, x
    result = (1 - lastx * modulus) // value
    return result + modulus if result < 0 else result

def keygen(N):
    '''Generate public and private keys from primes up to N.

pubkey, privkey = keygen(34)
msg = 123456789012345
coded = pow(msg, 65537, pubkey)
plain = pow(coded, privkey, pubkey)
assert msg == plain

    '''
    # http://en.wikipedia.org/wiki/RSA
    prime1 = gen_prime(N)
    prime2 = gen_prime(N)
    totient = (prime1 - 1) * (prime2 - 1)
    return prime1 * prime2, multinv(totient, 65537)

pubkey, privkey = keygen(32)
print("keys: public={}, private={}".format(pubkey, privkey))

keys: public=4567550543301076511, private=3040759113385555553

Use these keys to encrypt and decrypt a secret message. Note that pow expects an int.

msg = 359234562701343655
print("msg:       {:30}".format(msg))

encrypted = pow(msg, 65537, pubkey)
print("encrypted: {:30}".format(encrypted))

decrypted = pow(encrypted, privkey, pubkey)
print("decrypted: {:30}".format(decrypted))

assert msg == decrypted, "MISMATCH!"

msg:                   359234562701343655
encrypted:            2415327350779094472
decrypted:             359234562701343655

It would indeed be difficult to “guess” the dycrypted message from the encrypted value.

To send strings, we need to convert them to ints first.

def encrypt(msg, pubkey):
    encoded = int.from_bytes(msg, 'big')
    return pow(encoded, 65537, pubkey)

def decrypt(encrypted, pubkey, privkey):
    decrypted = pow(encrypted, privkey, pubkey)
    return decrypted.to_bytes(len(hex(decrypted)[2:])//2, 'big')

msg = b"iot49"

encrypted = encrypt(msg, pubkey)
decrypted = decrypt(encrypted, pubkey, privkey)

print("message:  ", msg)
print("encrypted:", encrypted)
print("decrypted:", decrypted)
assert msg == decrypted

message:   b'iot49'
encrypted: 146271442467418660
decrypted: b'iot49'

The code works as expected, but only for short messages (CPython fails with overflow, MicroPython silently):

msg = b"iot49 is awesome"

encrypted = encrypt(msg, pubkey)
decrypted = decrypt(encrypted, pubkey, privkey)

print("message:  ", msg)
print("encrypted:", encrypted)
print("decrypted:", decrypted)
if msg == decrypted:
    print("Success!")
else:
    print("Mismatch:  {} != {}".format(msg, decrypted))

message:   b'iot49 is awesome'
encrypted: 3736966150267381513
decrypted: b'!\xa7]pw\x88*.'
Mismatch:  b'iot49 is awesome' != b'!\xa7]pw\x88*.'

Now we can use PKC to transmit the AES key using the following steps:

  1. Recipient creates key pair & sends public key to the sender.

  2. Sender encodes message with public key and transmits the encrypted message.

  3. Recipient uses its private key to decrypt the AES key.

  4. Both parties communicate using AES encryption.

Although all information transmitted on the internet can potentially be read by an adversary, the encrypted message can only be recovered with the private key. Since that key is never (and, importantly, does not need to be) sent over the internet, the requirement for a “secure channel” is alleviated.

PKC takes lots of CPU cycles. Because of this it is usually used to transmit only small amounts of data and then switch to symmetric key encryption.

Man in the middle#

If you access a website (e.g. your bank) over the internet, how can you be sure it’s really your bank’s website and not a criminal that modified the information send? For example, if you are redirected to a website that looks like your bank’s you might enter your password, giving it to the crook.

PKC can help with this as well. The basic strategy is to

  1. The bank creates a key pair. When your browser connects, the bank sends the public key, called “certificate” in this use case.

  2. Your browser verifies the certificate:

    1. It check that the website encoded in the certificate (an extension of just a public key) matches your bank’s URL.

    2. It sends a “challenge” to the bank, basically a question that can only be answered if the private key is known. Only the bank has it, provided it is good at safeguarding it.

    3. It checks that the certificate is genuine and belongs to your bank.

The last step is tricky, since it requires some form of “secure channel”. In the simplest case the bank could give you the certificate at a safe place (e.g. visiting a branch). Then your browser can verify that the certificate received matches what the bank gave you.

Of course this approach is impractical. Because of this, browsers (and computer operating systems) come with a “built-in” collection of verified certificates. They also use chaining to limit the number of certificates that need be stored and avoid the need to get a new certificate each time a new website goes onling. The certificate received from the bank’s webserver is checked against these built-in certificates. If no match is found, the browser issues a warning (e.g. “Your connection is not private”) and refuses to connect.

This seems to work, but begs the question how you received your webbrowser and computer OS and if that procedure was safe …

Security is difficult, as we well know from almost daily breaches.