## 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ą zwykle 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ę właścicielem 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 iż łą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ą dzięki klucza prywatnego otrzymując wartość podpisu $$s$$. Weryfikujący samodzielnie wylicza wartość funkcji skrótu z przekazanego dokumentu, a następnie przekształca podpis dzięki klucza publicznego odzyskując skrót dokumentu wyliczony przez sygnatariusza. o ile 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 w tej chwili 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, iż 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. o ile 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.
```java
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.SecureRandom;
import java.security.Signature;
public class RSATest {
public static void main(String[] args) throws Exception {
byte[] message = "abcdefghijklmnoprstuwxyz1234567890!".getBytes();
// wygenerowanie kluczy
KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");
keyGen.initialize(2048, new SecureRandom());
KeyPair keyPair = keyGen.generateKeyPair();
// obiekt dla operacji podpisu cyfrowego
Signature signer = Signature.getInstance("SHA256withRSA");
// złożenie podpisu
signer.initSign(keyPair.getPrivate(), new SecureRandom());
signer.update(message);
byte[] signatureValue = signer.sign();
// weryfikacja podpisu
signer.initVerify(keyPair.getPublic());
signer.update(message);
System.out.println(signer.verify(signatureValue));
}
}
```
Praktycznie działanie podpisu cyfrowego RSA można wypróbować na [tej stronie](https://kjur.github.io/jsrsasign/sample/sample-ecdsa.html). 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](https://tools.ietf.org/html/rfc3447).
## 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 uproszczeniu 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](http://www.secg.org/SEC2-Ver-1.0.pdf), który zawiera propozycje krzywych eliptycznych do użycia w kryptografii.
```java
import java.security.KeyPair;
import java.security.KeyPairGenerator;
import java.security.SecureRandom;
import java.security.Signature;
import java.security.spec.ECGenParameterSpec;
public class ECDSATest {
public static void main(String[] args) throws Exception {
byte[] message = "abcdefghijklmnoprstuwxyz1234567890!".getBytes();
KeyPairGenerator keyGen = KeyPairGenerator.getInstance("EC");
keyGen.initialize(new ECGenParameterSpec("secp256r1"), new SecureRandom());
KeyPair keyPair = keyGen.generateKeyPair();
Signature signer = Signature.getInstance("SHA256withECDSA");
signer.initSign(keyPair.getPrivate(), new SecureRandom());
signer.update(message);
byte[] signatureValue = signer.sign();
signer.initVerify(keyPair.getPublic());
signer.update(message);
System.out.println(signer.verify(signatureValue));
}
}
```
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](https://kjur.github.io/jsrsasign/sample-ecdsa.html). Algorytmy kryptograficzne oparte o krzywe elpityczne opisane są w [RFC 6090](https://tools.ietf.org/html/rfc6090).
## 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ć, iż klucze publiczne, tak jak każde inne dane, również powinny podlegać procesowi uwierzytelnienia. Jaką mamy pewność, iż klucz publiczny należy do osoby, która go nam przekazała? Skąd wiemy, iż 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.
