lab4 zivvs

import random
from math import gcd

__author__ = "sashadereh"

SEQUENCE_LEN = 8
START_SEQUENCE_ELEMENT = 2
SEQUENCE_STEP = 4
MAX_SYMBOL_CODE = 2 ** SEQUENCE_LEN - 1
TEXT = "Hello. My name is Sasha Derekh"


def fill_backpacks(number, sequence):
    result = 0

    for num in sequence:
        if number & 1 == 1:
            result += num
        number >>= 1

    return result


def get_random_number(a_from, a_to):
    return random.randint(a_from + 1, a_to)


def generate_sequence():
    sequence = [START_SEQUENCE_ELEMENT]
    sum = 0
    for i in range(1, SEQUENCE_LEN, 1):
        sum += sequence[i - 1]
        sequence.append(sum + SEQUENCE_STEP)
    sum += sequence[-1]
    sequence = list(reversed(sequence))

    return sequence, sum


def generate_w(p):
    for i in range(2, p - 1):
        if gcd(i, p) == 1:
            return i

    return 0


def generate_u(w, p):
    for i in range(2 , p):
        if (w * i) % p == 1:
            return i
    return 0


def main():
    print("Source text: {}".format(TEXT))

    sequence, sequence_sum = generate_sequence()
    print("Generated sequence: {}, its sum = {}".format(sequence, sequence_sum))

    # Start "send"

    encoded_text = [ord(c) for c in TEXT]
    print("Encoded source text: {}".format(encoded_text))

    p = get_random_number(sequence_sum, sequence_sum * 3)
    print("Generated p = {}".format(p))

    w = generate_w(p)
    if w == 0:
        raise ValueError('w is 0')
    print("Generated w = {}".format(w))

    # Determine normal backpack sequence via (open key)
    # y = w * x (mod p)
    normal_backpack_sequence = [(w * i) % p for i in sequence]
    print("Generated normal backpack sequence: {}".format(normal_backpack_sequence))

    # Fill backpacks
    encrypted_text = [fill_backpacks(code, normal_backpack_sequence) for code in encoded_text]
    print("Encrypted text: {}".format(encrypted_text))

    # Start "receive"

    u = generate_u(w, p)
    if u == 0:
        raise ValueError('u is 0')
    print("Generated u = {}".format(u))

    # Determine encrypted sequence via
    # L = D * u
    # шифротекст нормального рюкзака -> шифротекст рюкзака sequence
    encrypted_message = [(value * u) % p for value in encrypted_text]

    # Decrypt message
    decrypted_encoded_message = []
    for encrypted_symbol in encrypted_message:
        decrypted_symbol_as_bits = ''
        for sequence_item in sequence:
            if encrypted_symbol >= sequence_item:
                decrypted_symbol_as_bits += "1"
                encrypted_symbol -= sequence_item
            else:
                decrypted_symbol_as_bits += "0"
        decrypted_encoded_message.append(int(decrypted_symbol_as_bits[::-1], 2))
    print("Encoded decrypted text: {}".format(decrypted_encoded_message))

    decrypted_text = [str(chr(i)) for i in decrypted_encoded_message]
    print("Decrypted text: {}".format(decrypted_text))


if __name__ == "__main__":
    main()