CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 52
Image: ubuntu2204
Tweet
Share
Share
Kernel: SageMath 10.1
from sage.all import GF, PolynomialRing, ZZ
from itertools import combinations

# Define the finite field and the polynomial ring
F = GF(256, 'a', modulus='primitive')
alpha = F.gen()
R = PolynomialRing(F, 's')

# Length of the original message (k) and the encoded message (n)
k = 8
n = 10

# Custom exception for unrecoverable messages
class UnrecoverableMessage(Exception):
    pass

# Encoding function
def baby_rs_encode(message: bytes) -> bytes:
    assert len(message) == k
    
    # Convert message bytes to field elements
    message_field_elements = [F.from_integer(byte) for byte in message]
    print("Message field elements:", message_field_elements)
    
    # Create the Lagrange interpolation polynomial
    points = [(alpha**i, message_field_elements[i]) for i in range(k)]
    g = R.lagrange_polynomial(points)
    
    # Evaluate the polynomial at n points
    encoded_message = [g(alpha**i).to_integer() for i in range(n)]
    print("Encoded message:", encoded_message)
    return bytes(encoded_message)

# Improved decoding function
def baby_rs_decode_improved(encoded_message: bytes) -> bytes:
    assert len(encoded_message) == n

    # Convert encoded message bytes to field elements
    encoded_field_elements = [F.from_integer(byte) for byte in encoded_message]

    for points_indices in combinations(range(n), k):
        print("Trying combination:", points_indices)
        points = [(alpha**i, encoded_field_elements[i]) for i in points_indices]
        g = R.lagrange_polynomial(points)
        print("Lagrange polynomial:", g)

        # Check if the polynomial can correctly reconstruct the original message
        decoded_message = [g(alpha**i).to_integer() for i in range(k)]
        if all(encoded_field_elements[i] == F.from_integer(decoded_message[i]) for i in range(k)):
            print("Decoded message:", decoded_message)
            return bytes(decoded_message)
        else:
            print("Failed combination:", points_indices)

    print("Raising UnrecoverableMessage exception")
    raise UnrecoverableMessage()

# Test the improved function
message = b'iloveyou'
expected_encoded_message = baby_rs_encode(message)
recoverable_encoded_message_1 = b'ilov3you\xa8\x98'
recoverable_encoded_message_2 = b'iloveyou\xa8#'
unrecoverable_encoded_message = b'il0v3you\xa8#'

try:
    decoded_message = baby_rs_decode_improved(expected_encoded_message)
    print("Decoded message from expected_encoded_message:", decoded_message)
    assert decoded_message == message, "Decoding of expected_encoded_message failed"
    
    decoded_message = baby_rs_decode_improved(recoverable_encoded_message_1)
    print("Decoded message from recoverable_encoded_message_1:", decoded_message)
    assert decoded_message == message, "Decoding of recoverable_encoded_message_1 failed"
    
    decoded_message = baby_rs_decode_improved(recoverable_encoded_message_2)
    print("Decoded message from recoverable_encoded_message_2:", decoded_message)
    assert decoded_message == message, "Decoding of recoverable_encoded_message_2 failed"
    
except AssertionError as e:
    print(e)
Message field elements: [a^6 + a^5 + a^3 + 1, a^6 + a^5 + a^3 + a^2, a^6 + a^5 + a^3 + a^2 + a + 1, a^6 + a^5 + a^4 + a^2 + a, a^6 + a^5 + a^2 + 1, a^6 + a^5 + a^4 + a^3 + 1, a^6 + a^5 + a^3 + a^2 + a + 1, a^6 + a^5 + a^4 + a^2 + 1] Encoded message: [105, 108, 111, 118, 101, 121, 111, 117, 168, 152] Trying combination: (0, 1, 2, 3, 4, 5, 6, 7) Lagrange polynomial: (a^6 + a^3 + a^2 + a + 1)*s^7 + (a^7 + a^6 + a^4 + a^3 + 1)*s^6 + (a^7 + a^6 + a^5 + a^3)*s^5 + (a^5 + a^4 + a^3 + a^2 + a + 1)*s^4 + (a^5 + a^4 + a^3 + a^2 + a + 1)*s^3 + (a^6 + a^3 + 1)*s^2 + (a^5 + a + 1)*s + a^6 + a^5 + a^4 + a^3 + a^2 + 1 Decoded message: [105, 108, 111, 118, 101, 121, 111, 117] Decoded message from expected_encoded_message: b'iloveyou' Trying combination: (0, 1, 2, 3, 4, 5, 6, 7) Lagrange polynomial: (a^6 + a^5 + a^3 + 1)*s^7 + (a^5 + a^3 + a^2 + 1)*s^6 + (a^6 + a^4 + a^2)*s^5 + (a^5 + a^4 + a^3 + 1)*s^4 + (a^6 + a^5 + a^2 + 1)*s^3 + (a^6 + a^5 + a^4 + a^2)*s^2 + (a^4 + a^3 + 1)*s + a^6 + a^3 Decoded message: [105, 108, 111, 118, 51, 121, 111, 117] Decoded message from recoverable_encoded_message_1: b'ilov3you' Decoding of recoverable_encoded_message_1 failed
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) Cell In [5], line 33 30 recoverable_encoded_message_2 = b'iloveyou\xa8#' 31 unrecoverbe_encoded_message = b'il0v3you\xa8#' ---> 33 assert baby_rs_encode(message) == expected_encoded_message 34 assert baby_rs_decode(expected_encoded_message) == message 35 assert baby_rs_decode(recoverable_encoded_message_1) == message AssertionError: