Szyfry (3). Liczby Sophie Germain a kryptografia

MM&AlK

W poprzedniej notce wspominaliśmy, że najtrudniejsze do rozłożenia na czynniki są liczby postaci
A = 2a + 1. Szczególne znaczenie mają w tym przypadku liczby pierwsze Sophie Germain. Liczby Sophie Germain to liczby pierwsze posiadające w swej strukturze liczbę pierwszą, a więc liczby mające postać:

p = 2p_n + 1, gdzie p, p_n są liczbami pierwszymi.

Jeżeli liczby pierwsze są postaci: p₁ = 2a + 1, p₂ = 2b + 1, gdzie a, b są liczbami złożonymi
i (a, b) ≠ 1, to iloczyn takich liczb pierwszych jest znaczne łatwiej rozłożyć na czynniki.
Jest bowiem bardzo często tak, że liczby a, b tworzące strukturę liczb pierwszych p₁ i p₂ mają wspólny dzielnik. Związane jest to z faktem, że co trzecia liczba w zbiorze liczb naturalnych dzieli się przez liczby będące wielokrotnością innych liczb pierwszych lub ich potęg. Tak więc istnieje wiele liczb pierwszych, w których liczby a, b posiadają wspólny dzielnik będący wielokrotnością liczby pierwszej lub będący potęgą liczby pierwszej (3, 5, 7, 11, ...) np.

7 = 2 x 3 + 1, 13 = 2 x 6 + 1, 31 = 2 x 15 + 1, 37 = 2 x 18 + 1, …
19 = 2 x 3² + 1, 109 = 4 x 3³ + 1, 487 = 2 x 3⁵ + 1, …
21 = 2 x 10 + 1, 31 = 2 x 15 + 1, 41 = 2 x 20 + 1, 61 = 2 x 30 + 1, ...
251 = 2 x 5³ + 1, 501 = 4 x 5⁶ + 1, ...
29 = 2 x 14 + 1, 71 = 2 x 35 + 1, 113 = 2 x 56 + 1, ... 1 373 = 4 x 7³ + 1, ...
23 = 2 x 11 + 1, 67 = 2 x 33 + 1, 89 = 2 x 44 + 1, 199 = 2 x 99 + 1, ...
2 663 = 12 x 11³ + 1, ...
53 = 2 x 26 + 1, 79 = 2 x 39 + 1, 131 = 2 x 65 + 1, 157 = 2 x 78 + 1, ...

Problem rozkładu liczb naturalnych na dwa czynniki, to problem od początków kształtowania się teorii liczb. P. Fermat podał następujący sposób znajdowania dla każdej liczby naturalnej nieparzystej n najmniejszej liczby naturalnej a, takiej iż a jest dzielnikiem n , n = ab i a ≥ b. Wyznaczamy największą liczbę naturalną r, taką iż r² < n i przyjmujemy d = n – r². Do – d dodajemy kolejno liczby 2r + 1, 2r + 3, 2r + 5, 2r + 7, …, 2r + 2k – 1, aż otrzymamy kwadrat liczby całkowitej nieujemnej q²; wówczas a = k + r + q będzie najmniejszą liczbą naturalną a taką, iż a będzie dzielnikiem n, n = ab i a ≥ b (W. Sierpiński, Teoria liczb cz. II str. 341). Metoda Fermata, znajdowania dwu czynników liczby naturalnej złożonej, wykorzystywana jest w metodzie sita kwadratowego stosowanej w kryptologii. Metoda Fermata jest ściśle związana z funkcją kwadratową…
Przyjrzyjmy się czynnikom liczby nieparzystej złożonej N...

N = A × B = A(A + 2k), gdzie k jest liczbą naturalną, B > A.

Jest zatem: A² + 2kA – N = 0.
Rozwiązujemy równanie kwadratowe względem A. Jest więc:

∆ = 4k² + 4N = 4(k² + N) = 4d; ∆^1/2 = 2(k² + N)^1/2 = 2d^1/2;

Pierwiastek z delty musi być liczbą naturalną... Traktując k chwilowo jak liczbę zmienną, szukamy takiej liczby k, dla której pierwiastek z delty jest liczbą naturalną… Pierwiastek równania czyli liczba A wynosi:

A = (∆^1/2 – 2k)/2 = (k² + N)^1/2 – k = d^1/2 – k.

Wobec B = A + 2k otrzymujemy: B = (k² + N)^1/2 + k = d^1/2 + k.
Jest zatem: N = A × B = (d^1/2 – k)(d^1/2 + k) = d – k² = (k² + N) – k² = N.
Rozwiązaniem jest: B = d^1/2 + k, A = d^1/2 – k.

Inne ciekawe przekształcenie…
Po dodaniu obustronnie liczby k² do równania N = A × B = A(A + 2k), gdzie k jest liczbą naturalną,
B > A, otrzymujemy:

N + k² = A² + 2Ak + k²; stąd: N + k² = (A + k)²; N + k² = d².

Tak więc szukamy takiej liczby k_x dla której pierwiastek z liczby N + k_x² jest liczba naturalną:

(N + k_x²)^1/2 = d.

Pewną odmianą metody Fermata i funkcji kwadratowej jest metoda wynikająca z hipotezy Goldbacha mówiącej, że każda liczba parzysta jest sumą dwóch liczb pierwszych. Jest wówczas:

2n = p₁ + p₂, gdzie p₁ = (n + m), p₂ = (n – m).

Dla iloczynu liczb mamy: N = p₁ x p₂ = (n + m)(n – m) = n² – m²; stąd: n² – N = m². Traktując n jak zmienną, szukamy takiej liczby n_x dla której pierwiastek z różnicy n_x²– N jest liczbą naturalną m. Jest wówczas:

(n_x² – N)^1/2 = m. Ostatecznie znajdujemy: p₁ = (n_x + m), p₂ = (n_x – m).

Bardzo ciekawie wygląda jeszcze inne przekształcenie:

N = A × B stąd: (N – A)/A = B – 1.

Jeżeli liczby pierwsze p₁, p₂ w swej strukturze mają wspólny dzielnik: p₁ = 2ad + 1 ; p₂ = 2bd + 1, gdzie a,b d, to liczby naturalne, wówczas otrzymujemy: (N – p₁)/(2dp₁) = b.
Przykład:
Dana jest liczba N = 10 362 031 rozłożyć liczbę N na dwa czynniki. Poszukujemy wspólnego dzielnika d.
W tym celu od Liczby N odejmujemy 1 i szukamy potęg liczb pierwszych przez która dzieli się liczba (N – 1). Liczba (N – 1) ma dzielniki: 2, 3, 5, 7³, 19, 53. Nas interesuje liczba 7³ = d. Przyjmujemy:
p₁ = 2 x 7³a_x + 1. Jest więc: [10 362 031 – (2 x 7³a_x + 1)]/[ 2 x 7³ x (2 x 7³a_x + 1)] = b. Przyjmując za a_x kolejne liczby naturalne szukamy takiej wartości a_x, dla której b jest liczbą naturalną. Możemy takie działania wykonać na arkuszu kalkulacyjnym lub napisać programik komputerowy. Bardzo szybko znajdziemy rozwiązanie, bowiem dla a_x = 2 otrzymujemy:

10 362 031 – (2 x 7³ x 2 + 1)]/[ 2 x 7³ x (2 x 7³ x 2 + 1)] = 11.

Zatem liczby pierwsze p₁, p₂ to:
p₁ = 4 x 7³ + 1 = 1373; p₂ = 2 x 7³ x 11 + 1 = 7547.

W notkach Szyfry (1), (2), (3) pokazaliśmy jak głęboko sięga ingerencja programistów i urzędów certyfikujących w kształt kluczy publicznych. Czynnik ludzki w procesie szyfrowania oraz firmy certyfikujące, to najsłabsze ogniwo… To dlatego rząd USA zabronił stosowania, w administracji państwowej, algorytmu RSA.

(w oparciu o ebook Zabawy z Pitagorasem, Fermatem i Goldbachem)