Podpis cyfrowy

Jednym z mechanizmów uwierzytelnienia jaki opisałem wcześniej są kody uwierzytelniające wiadomość w skrócie nazywane MAC. Przyszła pora na przedstawienie innego typu algorytmów, które umożliwiają realizację tej usługi. Będą to podpisy cyfrowe realizowane przez algorytmy asymetryczne (ang. asymmetric algorithms). W algorytmach tych występuje para kluczy. Dotychczas zajmowaliśmy się wyłącznie algorytmami symetrycznymi, w których występował wyłącznie klucz tajny.

Podpis odręczny i cyfrowy

Co łączy a co odróżnia podpis odręczny od jego odpowiednika w formie cyfrowej? Oba powinny być przypisane jednej osobie i niemożliwe do podrobienia. Podpisujący nie powinien mieć możliwości ich się wyprzeć. Powinny być również łatwe do utworzenia i łatwe do weryfikacji przez dowolną osobę. Podpis cyfrowy nie musi być fizycznie związany z dokumentem (może być przechowywany w innym pliku) i obejmuje zawsze całość dokumentu. Podpisy odręczne składane są zazwyczaj na ostatniej stronie dokumentu i są takie same dla wszystkich dokumentów jakie podpisujemy. Wartość podpisu cyfrowego zależy od dokumentu i zawsze obejmuje jego całość.

Algorytmy przeznaczone do podpisu cyfrowego składają się z trzech części: operacji generowania kluczy, operacji składania podpisu i operacji jego weryfikacji. Oczywiście raz wygenerowane klucze mogą służyć do złożenia wielu podpisów. Pojęcia podpisu cyfrowego i podpisu elektronicznego są często używane zamiennie. Podpis elektroniczny to dowolna forma podpisu zapisana elektronicznie. W takim znaczeniu skan podpisu odręcznego będzie podpisem elektronicznym. Podpis cyfrowy to podpis bazujący na mechanizmach kryptograficznych. W dalszej części skupię się na podpisach cyfrowych.

Klucz prywatny i publiczny

Używając algorytmów asymetrycznych użytkownik po wygenerowaniu kluczy staje się posiadaczem pary kluczy. Jeden z nich przeznaczony jest do przeprowadzenia operacji podpisu. Tylko właściciel pary kluczy powinien mieć możliwość wygenerowania podpisu dlatego ten klucz musi być utrzymany w sekrecie i stąd nazywa się go kluczem prywatnym (ang. private key). Drugi z kluczy używany jest w operacji weryfikacji podpisu. Mogą ją realizować wszyscy zainteresowani. Klucz przeznaczony do tego celu jest rozpowszechniany w formie jawnej i nazywa się go kluczem publicznym (ang. public key). Z klucza publicznego nie da się wyznaczyć klucza prywatnego mimo że łączą je zależności matematyczne. Wyrażając się bardziej precyzyjnie: operacja ta jest teoretycznie możliwa, ale przez swą złożoność obliczeniową niewykonalna w praktyce przy odpowiednio silnym kluczu.

Na rysunku poniżej przedstawiłem typowy schemat operacji podpisu. Podpisujący wylicza wartość funkcji skrótu z dokumentu i przekształca ją za pomocą klucza prywatnego otrzymując wartość podpisu $$s$$. Weryfikujący samodzielnie wylicza wartość funkcji skrótu z przekazanego dokumentu, a następnie przekształca podpis za pomocą klucza publicznego odzyskując skrót dokumentu wyliczony przez sygnatariusza. Jeżeli wyliczone wartości funkcji skrótu są równe to podpis odpowiada otrzymanemu dokumentowi i operacja weryfikacji kończy się powodzeniem. W przeciwnym przypadku dokument lub podpis zostały zmienione i wynik weryfikacji jest negatywny.

W tym momencie trzeba wyjaśnić z jakiego powodu podpis składany jest nie na dokumencie, ale na jego skrócie. Dzieje się tak ze względów bezpieczeństwa i wynika z zasad działania algorytmów asymetrycznych. Używanie funkcji skrótu uniemożliwia atak pozwalający na generowanie podpisów dla innych dokumentów na podstawie posiadanych już dokumentów z ich podpisami przez osobę nie będącą właścicielem klucza prywatnego. Aby dokładnie zrozumieć dlaczego taki atak jest możliwy niezbędne jest zajrzenie wgłąb algorytmów asymetrycznych.

Algorytm RSA

Kluczem prywatnym w algorytmie RSA (skrót pochodzi od nazwisk twórców: Rivest, Shamir, Adleman) jest para liczb $$(d, n)$$, kluczem publicznym para $$(e, n)$$. Liczba $$n$$ nazywana jest modułem i powstaje poprzez wyliczenie iloczynu dwóch dużych losowych liczb pierwszych $$p$$ i $$q$$ znalezionych na etapie generowania kluczy ($$n = p * q$$). Klucz prywatny powiązany jest z liczbami $$p$$ i $$q$$, dlatego muszą być one utrzymane w tajemnicy. Ich iloczyn jest składnikiem klucza publicznego, ale obecnie nie znamy efektywnych algorytmów faktoryzacji iloczynów dużych liczb pierwszych. Na tym problemie opiera się siła algorytmu RSA. Atakujący nie jest w stanie rozłożyć modułu na czynniki i wyznaczyć wartość $$d$$.

Złożenie podpisu na wiadomości $$M$$ odbywa się poprzez wyliczenie $$S = M^e mod n$$, operacją odwrotną jest $$M = S^d mod n$$. Zauważmy, że są to wzory matematyczne, a więc $$M$$ jest liczbą. Dodatkowo aby operacje przebiegały prawidłowo $$M$$ musi być mniejsze, niż $$n$$. To jeden z powodów konieczności używania funkcji skrótu dla podpisywanych dokumentów. Jeżeli składalibyśmy podpis na całym dokumencie należałoby podzielić go na części na przykład $$(M_1, M_2, M_3)$$ w taki sposób aby każda z nich spełniała podany warunek $$M$$ mniejsze, niż $$n$$. Dla podanego przykładu podpis również składałby się z trzech komponentów $$(S_1, S_2, S_3)$$. Na tej podstawie osoba nie będąca właścicielem klucza prywatnego może w prosty sposób wyznaczyć podpis dla dokumentu $$(M_3, M_2, M_1)$$. Będzie to $$(S_3, S_2, S_1)$$. Zastosowanie funkcji skrótu uniemożliwi taki atak.

Poniższy program, zaimplementowany w Java, w pierwszym etapie działania generuje parę kluczy RSA o długości 2048 bitów. W kolejnym kroku dla przykładowej wiadomości wylicza wartość podpisu cyfrowego używając funkcji skrótu SHA-256 (oznaczenie w kodzie SHA256withRSA). W tej operacji bierze udział klucz prywatny. Następnie podpis ten jest weryfikowany. W tym kroku używany jest już wyłącznie klucz publiczny.

1import java.security.KeyPair;
2import java.security.KeyPairGenerator;
3import java.security.SecureRandom;
4import java.security.Signature;
5 
6public class RSATest {
7    public static void main(String[] args) throws Exception {
8        byte[] message = "abcdefghijklmnoprstuwxyz1234567890!".getBytes();
9 
10        // wygenerowanie kluczy
11        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
12        keyGen.initialize(2048, new SecureRandom());
13        KeyPair keyPair = keyGen.generateKeyPair();
14 
15        // obiekt dla operacji podpisu cyfrowego
16        Signature signer = Signature.getInstance("SHA256withRSA");
17 
18        // złożenie podpisu
19        signer.initSign(keyPair.getPrivate(), new SecureRandom());
20        signer.update(message);
21 
22        byte[] signatureValue = signer.sign();
23 
24        // weryfikacja podpisu
25        signer.initVerify(keyPair.getPublic());
26        signer.update(message);
27 
28        System.out.println(signer.verify(signatureValue));
29    }
30}

Praktycznie działanie podpisu cyfrowego RSA można wypróbować na tej stronie. W ramach samodzielnych eksperymentów proponuję zakłócić wartość podpisu lub spróbować zweryfikować podpis pod zmienioną wiadomością. Warto również zaobserwować zależność pomiędzy długością klucza a czasem jego generacji. Szczegóły dotyczące działania i implementacji algorytmu RSA przedstawione są w RFC 3447.

Krzywe eliptyczne

Problem faktoryzacji to nie jedyny z trudnych obliczeniowo problemów wykorzystywanych w kryptografii klucza publicznego. W roku 1985 Neal Koblitz i Victor S. Miller zaproponowali użycie w kryptografii krzywych eliptycznych (ang. elliptic curves, w skrócie EC). Aby używać algorytmów opartych o krzywe eliptyczne należy wybrać określoną krzywą, która określona jest wzorem matematycznym. Parametr taki nazywa się parametrem domeny (ang. domain parameter). Kluczem publicznym na konkretnej krzywej eliptycznej jest jeden z wybranych na niej punktów.

Zamieszczony poniżej program pokazuje działanie algorytmu ECDSA (ang. Elliptic Curve Digital Signature Algorithm). W pierwszym etapie wygenerowana zostaje para kluczy z użyciem krzywej eliptycznej oznaczonej nazwą secp256r1. Następnie następują operacje złożenia i weryfikacji podpisu. Wzór użytej krzywej można odnaleźć w dokumencie Recommended Elliptic Curve Domain Parameters, który zawiera propozycje krzywych eliptycznych do użycia w kryptografii.

1import java.security.KeyPair;
2import java.security.KeyPairGenerator;
3import java.security.SecureRandom;
4import java.security.Signature;
5import java.security.spec.ECGenParameterSpec;
6 
7public class ECDSATest {
8    public static void main(String[] args) throws Exception {
9        byte[] message = "abcdefghijklmnoprstuwxyz1234567890!".getBytes();
10 
11        KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC");
12        keyGen.initialize(new ECGenParameterSpec("secp256r1"), new SecureRandom());
13        KeyPair keyPair = keyGen.generateKeyPair();
14 
15        Signature signer = Signature.getInstance("SHA256withECDSA");
16 
17        signer.initSign(keyPair.getPrivate(), new SecureRandom());
18        signer.update(message);
19 
20        byte[] signatureValue = signer.sign();
21 
22        signer.initVerify(keyPair.getPublic());
23        signer.update(message);
24 
25        System.out.println(signer.verify(signatureValue));
26    }
27}

Długość klucza określonego na krzywej eliptycznej określa się na podstawie wybranej krzywej. Ta użyta w przykładowym programie umożliwia generowanie kluczy o długości 256 bitów. Pod względem bezpieczeństwa odpowiada to kluczowi o długości 3072 bitów algorytmu RSA. Ponieważ wyraźnie krótsze klucze zapewniają ten sam poziom bezpieczeństwa algorytmy oparte o krzywe eliptyczne zyskują na popularności.

Z generowaniem kluczy i działaniem algorytmu podpisu ECDSA można również poeksperymentować na tej stronie. Algorytmy kryptograficzne oparte o krzywe elpityczne opisane są w RFC 6090.

Podsumowanie

Algorytmy asymetryczne upraszczają proces wymiany klucza pomiędzy stronami ponieważ klucz publiczny jest jawny, a klucz prywatny nie jest współdzielony i nie ma konieczności tworzenia zabezpieczonego kanału do jego przekazania. Jest to duża zaleta tego typu mechanizmów. Trzeba jednak pamiętać, że klucze publiczne, tak jak każde inne dane, również powinny podlegać procesowi uwierzytelnienia. Jaką mamy pewność, że klucz publiczny należy do osoby, która go nam przekazała? Skąd wiemy, że ta osoba jest również właścicielem klucza prywatnego do przekazanego nam klucza publicznego? Rozwiązaniem tego problemu będzie dokładnie ten sam mechanizm, który opisałem powyżej. Klucze publiczne mogą również być opatrzone podpisem cyfrowym. Taki dokument, uzupełniony o dane identyfikujące właściciela danego klucza publicznego, nazywamy certyfikatem klucza publicznego (ang. public key certificate). Przedstawię je dokładniej w jednym z kolejnych wpisów.