• 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?

Ultraszybki serwer VPS NVMe START
0 głosów
107 wizyt
pytanie zadane 21 października w Python, Django przez Deloryn Użytkownik (710 p.)
edycja 21 października 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ź

+2 głosów
odpowiedź 22 października przez Gynvael Coldwind Dyskutant (8,300 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 przez Benek Nałogowiec (41,600 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 przez Deloryn Użytkownik (710 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 przez Gynvael Coldwind Dyskutant (8,300 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 przez Deloryn Użytkownik (710 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 przez Gynvael Coldwind Dyskutant (8,300 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 przez Deloryn Użytkownik (710 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 przez Gynvael Coldwind Dyskutant (8,300 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 przez Deloryn Użytkownik (710 p.)
Oki, postaram się przyjrzeć tej konwersji :)

Podobne pytania

+1 głos
2 odpowiedzi 85 wizyt
pytanie zadane 21 kwietnia w Bezpieczeństwo, hacking przez arek01996 Stary wyjadacz (11,740 p.)
+1 głos
2 odpowiedzi 92 wizyt
pytanie zadane 17 listopada 2015 w Python, Django przez Devero Początkujący (300 p.)
0 głosów
0 odpowiedzi 147 wizyt

41,279 zapytań

80,219 odpowiedzi

158,694 komentarzy

19,707 pasjonatów

Przeglądających: 244
Pasjonatów: 19 Gości: 225

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...