• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Python - szyfrowanie RSA. Dlaczego program nie działa?

VPS Starter Arubacloud
0 głosów
1,760 wizyt
pytanie zadane 21 października 2017 w Python przez Deloryn Bywalec (2,060 p.)
edycja 21 października 2017 przez Deloryn

Cześć. Próbuję sobie robić po kolei zadania z wielkiej listy wyzwań i mam do napisania program szyfrujący / deszyfrujący. Wybrałem sobie algorytm RSA. Kod napisałem samodzielnie, oczywiście patrząc na algorytmy w Internecie. Korzystałem z tych stron: 

algorytm RSA 

rozszerzony algorytm Euklidesa

Widzę, że zaszyfrowana wiadomość (encrypted_message) to w moim przypadku po prostu znaki zamienione na kody ASCII. Dlaczego szyfrowanie nie działa? Błąd może być możliwe w generate_keys(), ale co robię nie tak? A jeśli nie ta funkcja, to może w rsa_encryption()? Oto kod:

 

#EDIT: znalazłem jedną maleńką rzecz. Wstawiam poprawiony kod. Zdaje się, że wiadomość można zaszyfrować poprawnie. Ale wiadomość nadal się nie deszyfruje poprawnie

# ----------------------
# Copyright (c) Deloryn
# ----------------------
from math import pow

# for this task I just take two small prime numbers - p = 11 and q = 13
def generate_keys(p, q):
    euler_function = (p - 1) * (q - 1)
    n = p * q # n is a module
    e = 1
    d = 1
    for i in range(2, n):
        if lcd(i, euler_function) == 1 and i % 2 != 0:
            e = i
            break

    j = 1
    while True:
        solution = extended_euclidean_algorithm(j,e)
        if solution != "No solution":
            d = solution
            break
        j += 1

    # now (e, n) is our public key and (d, n) is our private key
    return [e, n, d]


def rsa_encryption(message, e, n):
    encrypted_message = ""
    for letter in message:
        t = ord(letter)
        c = int((pow(t, e)) % n)
        encrypted_message += (str(c) + " ")
    return encrypted_message


def rsa_decryption(encrypted_message, d, n):
    encrypted_sign = ""
    decrypted_message = ""
    for character in encrypted_message:
        if character != " ":
            encrypted_sign += character
        else:
            t = int((pow(int(encrypted_sign), d)) % n) # t is a decrypted sign
            encrypted_sign = ""
            decrypted_message += chr(t)
    return decrypted_message


def lcd(a,b):  # Largest Common Divisor

    while b != 0:
        c = a % b
        a = b
        b = c
    return a


def extended_euclidean_algorithm(a, b):
    u = 1
    w = a
    x = 0
    z = b

    while w != 0:
        if w < z:
            pom = u
            u = x
            x = pom

            pom = w
            w = z
            z = pom

        q = int(w / z)
        u = u - q * x
        w = w - q * z

    if z != 1:
        return "No solution"

    if x < 0:
        x += b

    return x


message = "I like tea"
keys = generate_keys(11, 13)
encrypted_message = rsa_encryption(message, keys[0], keys[1])
decrypted_message = rsa_decryption(encrypted_message, keys[2], keys[1])

print("A message before RSA encryption: " + message)
print("A message after RSA encryption: " + encrypted_message)
print("A message after RSA decryption: " + decrypted_message)

 

1 odpowiedź

+1 głos
odpowiedź 22 października 2017 przez Gynvael Coldwind Nałogowiec (26,850 p.)

Na początek standardowy disclaimer: nigdy, przenigdy nie używaj crypto zaimplementowanego przez siebie do ważnych rzeczy, ani nie wymyślaj własnego crypto (chyba, że masz doktorat z crypto).

OK, skoro to mamy za sobą, to dwie rzeczy:

  • Źle wyliczasz "d" z jakiegoś powodu (nie wgłębiałem się w implementacje wyliczania d). Najlepiej wejdź sobie na angielską wiki od RSA i podstaw przykładowe wartości, które tam mają do testów - wtedy od razu wychodzi co jest OK, a co niezbyt.
  • Nie korzystaj z math.pow(a,b) % c, tylko ze zwykłego pow (nie tego z math, więc musisz swój import usunąć), a konkretniej pow(a, b, c). To ostatnie jest zoptymalizowane pod potęgowanie modulo.
komentarz 22 października 2017 przez Benek Szeryf (90,690 p.)

(...) nigdy, przenigdy nie używaj crypto zaimplementowanego przez siebie do ważnych rzeczy (...)

Chodzi Ci o to, że można to błędnie zaimplementować? Pobierając gotowca też nie mamy pewności, czy nie siedzi w nim backdoor.

komentarz 22 października 2017 przez Deloryn Bywalec (2,060 p.)
Dzięki za odpowiedź. Właściwie już udało mi się doprowadzić to do ładu, zostało najwyżej obsłużyć jakieś wyjątki - np. gdy p i q jest zbyt niskie.

Ale akurat co do tej ostatniej rzeczy: tak, próbowałem dać pow z trzema argumentami. Ale wywalalo błąd. Koniec końców zostałem przy liczba1 ** liczba2 % liczba3 i działa. Teraz jestem na telefonie, potem może wstawię poprawiony kod
2
komentarz 22 października 2017 przez Gynvael Coldwind Nałogowiec (26,850 p.)

@Benek

Nie tyle "można błędnie zaimplementować", co praktycznie na pewno się błędnie zaimplementuje ;)

Ad backdoor - i tak, i nie. Są pewne biblioteki od crypto, które co chwile są przeglądane przez sporo mądrych osób (np. OpenSSL), i są w całkiem niezłym stanie zarówno od strony implementacji, jak i "potencjalnego braku backdoorów". To nie znaczy, że jest 100% gwarancji, że nie ma w nich bugów ani backdoorów (ba, co jakiś czas ktoś coś znajduje, nawet w OpenSSL), ale prawdopodobieństwo jest znośne (tj. lepsze niż gdybyśmy sami implementowali).

Przy czym oczywiście nie chodzi mi o to, żeby nie implementować dla celów edukacyjnych/rozwojowych - jak najbardziej warto to robić. Po prostu nie używajmy tego co napiszemy na produkcji ;)

@Deloryn

Hmm, z jakiej wersji Pythona korzystasz? Jak testowałem Twój kod to zmieniłem math.pow na zwykły pow tak jak pisałem, i wszystko działało OK (a dla tego co piszę w kolejnym zdaniu jest bardzo istotne, żeby robić "potęgowanie modulu", a nie "potęgowanie" i "modulo" - rozbicie tych operacji baardzo podnosi złożoność obliczeniową i pamięciową całości, do tego stopnia, że przy sensownych kluczach po prostu nie da się tego stosować).

Ah, i druga sprawa - w RSA nie szyfruje się pojedynczych znaków, tylko przekształca się wiadomość w jedną dużą liczbę i operuje na niej. W innym wypadku (tj. w wypadku Twojego kodu) z RSA wychodzi Ci zwykły szyfr podstawieniowy, a tego typu szyfry są trywialnie łamalne dla odpowiednio długich wiadomości.

Też by się przydało rzucić okiem jak się robi padding dla RSA.

komentarz 22 października 2017 przez Deloryn Bywalec (2,060 p.)
Wielkie dzięki za rady :) później jak będę miał okazję, to sprawdzę. Faktycznie, mogłem robić math.pow. A podałbyś jakiś przykład? Bo załóżmy, że zakoduję całą wiadomość jako jedno. Nawet jeśli to odkoduję, to jak mam to potem przerobić na poprzedni tekst?
1
komentarz 22 października 2017 przez Gynvael Coldwind Nałogowiec (26,850 p.)

Napisałem Ci przykładowy kod poniżej - metoda 2 (_hack) to coś co zazwyczaj pisze jak potrzebuje to na szybko zaimplementować; metoda 1 jest bardziej "prawilna" ;)

Edit: ah, tak ogólnie wysokopoziomowo możesz myśleć o tym jako o "interpretacji tablicy bajtów jako liczby w systemie liczbowym o podstawie K=256" - takie spojrzenie na to trochę pomaga (no, przynajmniej mi pomogło ;p).

# Python 2
def str2num(s):
  s = bytearray(s)  # Zeby nie uzywac ord/chr
  n = 0
  for v in s:
    n *= 0x100
    n += v
  return n

def num2str(n):
  o = []
  while n != 0:
    o.append(chr(n % 0x100))  # ew. n & 0xff, ale to nie robi roznicy
    n /= 0x100 # ew. n >>= 8, ale to tez nie robi roznicy
  return ''.join(o)[::-1]

# Te metody nie przejda w tej formie w Python 3 przez .encode i .decode
def str2num_hack(s):
  return int(s.encode("hex"), 16)

def num2str_hack(n):
  return hex(n).replace("L", "")[2:].decode("hex")

text = "Witaj Swiecie"

enc_test1 = str2num(text)
dec_test1 = num2str(enc_test1)

enc_test2 = str2num_hack(text)
dec_test2 = num2str_hack(enc_test2)

print "Text:", text

print "Metoda 1 (kodowanie)  :", enc_test1
print "Metoda 1 (dekodowanie):", dec_test1

print "Metoda 2 (kodowanie)  :", enc_test2
print "Metoda 2 (dekodowanie):", dec_test2

Wynik:

gynvael:haven-windows> python test.py
Text: Witaj Swiecie
Metoda 1 (kodowanie)  : 6925486760194546946734326770021
Metoda 1 (dekodowanie): Witaj Swiecie
Metoda 2 (kodowanie)  : 6925486760194546946734326770021
Metoda 2 (dekodowanie): Witaj Swiecie

komentarz 23 października 2017 przez Deloryn Bywalec (2,060 p.)

Dzięki za przykład. Mógłbyś jeszcze trochę bardziej przyziemnie wyjaśnić mi działanie kodu?

Patrzę na to tak:
1) str2num(s) zamienia wiadomość na jedną dużą liczbę do zaszyfrowania. Natomiast co robi n *= 0x100? Chodzi o jakieś przesunięcie bitów?
2) num2str(n) zamienia odszyfrowaną liczbę z powrotem na wiadomość
3) str2num_hack(s) i num2str_hack(n) to jest to samo, co wyżej, tylko inaczej?

Wstawiam jeszcze mój obecny kod, jak mówiłem:
 

# ----------------------
# Copyright (c) Deloryn
# ----------------------


def generate_keys(p, q):
    euler_function = (p - 1) * (q - 1)
    n = p * q # n is a module
    e = look_for_public_exponent(euler_function, n) # e is a public exponent

    solution = extended_euclidean_algorithm(e, euler_function)
    if solution != "No solution":
        d = solution
        return [e, n, d]
    # now (e, n) is our public key and (d, n) is our private key


def rsa_encryption(message, e, n):
    encrypted_message = ""
    for letter in message:
        t = ord(letter)
        c = int(t**e % n)
        encrypted_message += (str(c) + " ")
    return encrypted_message


def rsa_decryption(encrypted_message, d, n):
    encrypted_sign = ""
    decrypted_message = ""
    for character in encrypted_message:
        if character != " ":
            encrypted_sign += character
        else:
            c = int(encrypted_sign)
            t = int(c**d % n) # t is a decrypted sign
            encrypted_sign = ""
            decrypted_message += chr(t)
    return decrypted_message


def lcd(a,b):  # Largest Common Divisor

    while b != 0:
        c = a % b
        a = b
        b = c
    return a


def look_for_public_exponent(euler_function, n):
    for i in range(2, n):
        if lcd(i, euler_function) == 1 and i % 2 != 0:
            e = i
            return e



def extended_euclidean_algorithm(a, b):
    u = 1
    w = a
    x = 0
    z = b

    while w != 0:
        if w < z:
            pom = u
            u = x
            x = pom

            pom = w
            w = z
            z = pom

        q = int(w / z)
        u = u - q * x
        w = w - q * z

    if z != 1:
        return "No solution"

    if x < 0:
        x += b

    return x


message = "I like tea"
keys = generate_keys(11, 13) # for this task I just take two small prime numbers - p = 11 and q = 13
encrypted_message = rsa_encryption(message, keys[0], keys[1])
decrypted_message = rsa_decryption(encrypted_message, keys[2], keys[1])

print("A message before RSA encryption: " + message)
print("A message after RSA encryption: " + encrypted_message)
print("A message after RSA decryption: " + decrypted_message)

 

1
komentarz 23 października 2017 przez Gynvael Coldwind Nałogowiec (26,850 p.)
Ad 1) Pisałeś kiedyś konwersje string→int? Jeśli tak, to to jest dokładnie to samo. Jeśli nie, to rzuć okiem jak się to pisze :) Po prostu podstawa systemu to 0x100 zamiast 10. Natomiast myślenie o tym jako o przesunięciu bitowym też jest akurat w tym wypadku poprawne.

Ad 2) Yup, czyli de facto rozbija liczbę na poszczególne bajty.

Ad 3) Tak - z jakiegoś powodu szybciej mi jest to tak implementować jak mi się spieszy (mniej myślenia) ;)
komentarz 24 października 2017 przez Deloryn Bywalec (2,060 p.)
Oki, postaram się przyjrzeć tej konwersji :)

Podobne pytania

0 głosów
1 odpowiedź 295 wizyt
pytanie zadane 20 listopada 2018 w Python przez pretorianin Nowicjusz (170 p.)
0 głosów
2 odpowiedzi 391 wizyt
pytanie zadane 17 lutego 2019 w PHP przez _Visni4PL_ Obywatel (1,320 p.)
+1 głos
2 odpowiedzi 498 wizyt
pytanie zadane 21 kwietnia 2017 w Bezpieczeństwo, hacking przez arek01996 Stary wyjadacz (12,100 p.)

92,454 zapytań

141,262 odpowiedzi

319,089 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...