[WikiDyd] [TitleIndex] [WordIndex

Cel zajęć

Celem zajęć jest praktyczne zapoznanie się z algortmem szyfrowania asymetrycznego na przykładzie RSA.

Wprowadzenie

Algorytm RSA jest wdzięcznym obiektem do ćwiczeń. Prosta budowa, a jednocześnie kilka kluczowych trudności powodują, że nawet w krótkim czasie zajęć można osiągnąć ciekawy wynik.

Uwaga 1. Algorytm operuje na liczbach, a nie znakach - dlatego przez szyfrowaniem potrzebne jest przekształcenie ciągu znaków w wektor. Długość bloku(liczby) nie może być większa od n, ale jednocześnie nie powinna być zbyt krótka, bo wtedy niebezpiecznie zbliżamy się do szyfrów historycznych.

Uwaga 2. Generowanie kluczy (e,n) i (d,n) to zadanie składające się z kilku kroków:

  1. wylosowanie liczb pierwszych p i q
  2. obliczenie n = p*q

  3. losowe wybranie e, które jest względnie pierwsze z (p-1)(q-1),
  4. obliczenie d będącego odwrotnością e modulo (p-1)(q-1)

Uwaga 3. Zrealizowanie szyfrowania i deszyfrowanie jest bardzo proste, ale taki algorytm jest bardzo niewydajny.

enc = (msg ** e) % n
msg = (enc ** d) % n

Są znacznie lepsze algorytmy podnoszenia do wysokich potęg. Poczytaj o nich.

Uwaga 4. Biblioteka kryptograficzna PyCrypto udostępnia profesjonalne wsparcie dla wykorzystania algorytmu RSA. Należy zawsze pamiętać, że lepiej jest skorzystać z gotowej, popularnej biblioteki niż samodzielnie implementować algorytm, nawet jeśli wydaje się on bardzo prosty.

from Crypto.PublicKey import RSA

# Tworzenie kluczy RSA
rsa_keys = RSA.generate(1024)

# Wydzielenie klucza publicznego
pub_key = rsa_keys.publickey()

# Zaszyfrowanie przy pomocy klucza publicznego
encrypted = pub_key.encrypt("Top secret", "some randomness") 

# Odszyfrowanie kluczem prywatnym
print rsa_keys.decrypt(encrypted)

Potrzebna wiedza

Podstawy programowania w języku Python, znajomość algorytmu Euklidesa, znajomość algorytmu RSA.

Dodatkowe informacje

Algorytm RSA jest bardzo dobrze opisany w każdej książce o kryptografii.

Kilka odnośników na początek:

Hasła dla Google: RSA

Przykładowe zadania

  1. Napisz funkcje, która będzie przekształcać tekst w wektor liczb o określonej długości. Określ ilość znaków, którą chcesz kodować jednocześnie.
  2. Napisz funkcje odwrotną, czyli przekształcającą wektor liczb w tekst.
  3. Zaimplementuj prosty test pierwszości dla liczby (np. sito Erastotenesa, test Fermata).
  4. Zaimplementuj algorytm Euklidesa do sprawdzenia największego wspólnego dzielnika.
  5. Napisz funkcję wykorzystającą algorytm Euklidesa do sprawdzenia czy liczby są względnie pierwsze.
  6. Napisz funkcję wykorzystającą algorytm Euklidesa do obliczenia liczby odwrotnej modulo.
  7. Zaimplementuj algorytm szybkiego potęgowania w artmetyce modularnej.
  8. Napisz pełny program generujący klucze RSA.
  9. Napisz program realizujący szyfrowanie RSA.
  10. Napisz program korzystający z PyCrypto do szyfrowania plików. Zaproponuj metodę ochrony klucza prywatnego.


2015-09-23 06:44