8. PAVYZDYS IŠ KRIPTOGRAFIJOS

Kriptografija yra kriptologijos dalis, nagrinėjanti informacijos šifravimo bei dešifravimo būdus. Ju_{‘} yra daug. Mes panagrinėsime viena_{‘} iš ju_{‘}.

1. Kiekvienam tekste T naudojamam simboliui (simboliu_{‘} grupei) vienareikšmiškai priskirkime viena_{‘} iš ℤ_{n} elementu_{‘}.

2. Skaičius n turėtu_{‘} tenkinti šias sa_{‘}lygas:

a) n = p · q – dvieju_{‘} dideliu_{‘} pirminiu_{‘} skaičiu_{‘} sandauga;

b) p ir q turėtu_{‘} būti tokie dideli pirminiai skaičiai, kad net pasitelkus kompiuterius, reiktu_{‘} labai daug laiko skaičiui n suskaidyti dauginamaisiais. Pavyzdžiui, šie skaičiai p ir q galėtu_{‘} turėti po 100 dešimtainiu_{‘} skaitmenu_{‘}.

3. Kadangi φ(n) = φ(p · q) = (p − 1)(q − 1), todėl parinkime toki_{‘} skaičiu_{‘} E taip, kad

DBD (E, φ(n)) = 1,

t.y.

DBD (E, p − 1) = DBD (E, q − 1) = 1.

4. Iš skaičiaus E apibrėžimo matome, kad E ∈ U_{φ(n)}, todėl galime rasti D = E^{−1} (mod φ(n)) : DE ≡ 1 (mod (p − 1)(q − 1)).

Parametrai n, p, q, E, D apibrėžia mūsu_{‘} teksto T i_{‘}slaptinimo-išslap-tinimo kriptosistema_{‘}. Skaičiai p, q ir D turėtu_{‘} būti i_{‘}slaptinti, o skaičiu_{‘} n ir E būtina neslėpti.

Kaip minėjome, teksta_{‘} (arba jo dali_{‘}), kuri_{‘} i_{‘}slaptine_{‘} norime perduoti, reikšime žiedo ℤ_{n} elementu x ∈ ℤ_{n}. Ši_{‘} elementa_{‘} x i_{‘}slaptinsime naudodamiesi bijektyvia funkcija e : ℤ_{n} → ℤ_{n}:

e(x) = x^{E} (mod n).

Teksto gavėjas, žinodamas skaičiu_{‘} D ir norėdamas išslaptinti e(x) ∈ ℤ_{n}, turėtu_{‘} pasinaudoti bijektyvia funkcija d : ℤ_{n} → ℤ_{n}:

d(y) = y^{D} (mod n).

d(e(x)) = (x^{E})^{D} (mod n) ≡ x^{ED} (mod n) = x^{1+φ(n)·k} =
= (x^{φ(n)})^{k}x ≡ x (mod n).

._{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.} _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}  _{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}_{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}_{.} siuntėjas  gavėjas e(x)  d(e(x))

Išnagrinėkime konkretesni_{‘} pavyzdi_{‘}. Kiekviename lietuviu_{‘} kalba parašytame tekste naudojamam simboliui vienareikšmiškai priskirkime žiedo ℤ_{33} elementa_{‘}

a 00 a_{‘} 01 b 02 c 03 č 04
d 05 e 06 e_{‘} 07 ė 08 f 09
g 10 h 11 i 12 i_{‘} 13 y 14
j 15 k 16 l 17 m 18 n 19
o 20 p 21 r 22 s 23 š 24
t 25 u 26 u_{‘} 27 ū 28 v 29
z 30 ž 31.

Taigi n = 33 = 3 · 11, φ(33) = 20. Parinkime E = 7, DBD (7, 20) = 1. Tada D ≡ E^{−1} (mod 20) = 3.

Tekstas, kuri_{‘} norime perduoti, yra žodis M =,,matematika“. Kiekvienai raidei vienareikšmiškai priskyre_{‘} kūno ℤ_{33} elementa_{‘}, gausime teksta_{‘} M =,,18002506180025121500“.

Pastebėsime, kad prieš i_{‘}slaptinant labai ilga_{‘} teksta_{‘}, galima ji_{‘} suskaidyti i_{‘} blokus M = M_{1}M_{2} … M_{k} taip, kad kiekviena iš šiu_{‘} bloku_{‘} M_{i}, 1 ⩽ i ⩽ k, skaitiniu_{‘} reikšmiu_{‘} neviršytu_{‘} n: 0 ⩽ M_{i} ⩽ n − 1. Pavyzdžiui, jeigu n yra 100 skaitmenu_{‘} dešimtainis skaičius, tai bloko M_{i} ilgis galėtu_{‘} būti net 10^{100}.

Mūsu_{‘} atveju M_{1} = 18, M_{2} = 00, M_{3} = 25, M_{4} = 06, M_{5} = 18, M_{6} = 00, M_{7} = 25, M_{8} = 12, M_{9} = 15, M_{10} = 00.

I_{‘}slaptine_{‘} kiekviena_{‘} M_{i}, 1 ⩽ i ⩽ 10, e(M_{i}) = M^{E} = C_{i}, gausime

tekstas  m a t e m a t i k a
i  1 2 3 4 5 6 7 8 9 10
M_{i}  18 00 25 06 18 00 25 12 15 00
C_{i} = M_{i}^{7} (mod 33) 06 00 31 30 06 00 31 12 27 00

Siuntėjas, norėdamas išslaptinti gauta_{‘} teksta_{‘} C = C_{1}C_{2} … C_{10}, turėtu_{‘} pasinaudoti funkcija d : ℤ_{33} → ℤ_{33} : d(C_{i}) = C_{i}^{3} ≡ M_{i} (mod 33).

I_{‘}vertinkime sunkumus, kuriuos tektu_{‘} i_{‘}veikti nežinant i_{‘}slaptintu_{‘} parametru_{‘} p, q ir D, bet norint išslaptinti teksta_{‘} C.

Galimi du būdai. Pirmasis – bandymas surasti skaičiu_{‘} D ≡ E^{−1} (mod ((p − 1)(q − 1))). Tam reiktu_{‘} žinoti skaičius p ir q. Bet jeigu šie skaičiai labai dideli, tai skaičiaus n = p·q skaidymas dauginamaisiais užims labai daug laiko.

Antrasis – pabandyti rasti φ(n) reikšme_{‘}, o tada ir išspre_{‘}sti lygini_{‘} D · E ≡ 1 (mod φ(n)). Tiesa, ir šis būdas ne ka_{‘} lengvesnis negu skaičiaus n skaidymas dauginamaisiais.

Žinodami φ(n) reikšme_{‘}, skaičius p ir q galime rasti ir taip:

\begin{aligned}φ(n) & = (p − 1)(q − 1) = pq − (p + q) + 1 = n − (p + q) + 1. \\ (p − q)^{2} & = (p + q)^{2} − 4pq = (p + q)^{2} − 4n. \end{aligned}

Taigi žinodami φ(n) ir n, galėtume rasti p + q ir p − q, taip pat ir skaičius p ir q (spre_{‘}sdami paprasčiausia_{‘} lygčiu_{‘} sistema_{‘}).

Pateiksime dar viena_{‘} kinu_{‘} teoremos taikymo pavyzdi_{‘}.

Tegu f_{1}(x), f_{2}(x), …, f_{n}(x) yra polinomai su sveikaisiais koeficientais ir mes norime atlikti aritmetinius veiksmus su jais kokioje nors šiu_{‘} polinomu_{‘} aritmetinėje išraiškoje I = I[f_{1}(x), f_{2}(x), …, f_{n}(x)]. Šiu_{‘} veiksmu_{‘} rezultata_{‘} išraiškoje I[f_{1}(x), f_{2}(x), …, f_{n}(x)] pažymėkime res(x).

Sakykime, res(x) ∈ Z[x] ir galime i_{‘}vertinti polinomo res(x) = a_{t}x^{t} + a_{t−1}x^{t−1} + … + a_{0} koeficientus: 0 ⩽ |a_{i}| ⩽ m = m_{1}m_{2} … m_{l}, 0 ⩽ i ⩽ t, DBD(m_{α}, m_{β}) = 1, α ≠ β.

Apibrėžkime polinomo f(x) = b_{r}x^{r} + b_{r−1}x^{r−1} + … + b_{0} ∈ Z[x] redukavimo veiksma_{‘} moduliu m kaip funkcija_{‘} r_{m} : Z[x] → Z_{m}[x], r_{m}(f(x)) = r_{m}(b_{r}x^{r} + b_{r−1}x^{r−1} + … b_{0}) = K_{b_{r}}x^{r} + K_{b_{r−1}}x^{r−1} + … + K_{b_{0}} = b̄_{r}x^{r} + b̄_{r−1}x^{r−1} + … + b̄_{0}.

Aritmetinius veiksmus išraiškoje I pakeiskime aritmetiniais veiksmais paprastesnėse išraiškose

I_{m_{j}}[r_{m_{j}}(f_{1}(x)), r_{m_{j}}(f_{2}(x)), …, r_{m_{j}}(f_{n}(x))],

o šiu_{‘} veiksmu_{‘} rezultata_{‘} pažymėkime res_{m_{j}}(x), 1 ⩽ j ⩽ l. Polinoma_{‘} res (x) galėsime rasti, išsprende_{‘} sistema_{‘}

res(x) ≡ res_{m_{j}}(x) (mod m_{j}), j = 1, 2, …, l.

Visa_{‘} šia_{‘} procedūra_{‘} galima pavaizduoti diagrama:

Z[x]  Z_{m_{j}}[x]
Išraiška ⟶ Redukuota išraiška
I[f_{1}, …, f_{n}]  I_{m_{j}}[r_{m_{j}}(f_{1}), …, r_{m_{j}}(f_{n})]

Veiksmai Z ↓|  ↓ Veiksmai mod m_{j} |

Rezultatas  ⟵  Redukuotas rezultatas
res(x)  Sistemos  res_{m_{j}}(x)

res(x) = res_{m_{j}}(x) sprendimas

6.37 pavyzdys. Sakykime, norime sudauginti du polinomus f_{1}(x) = 7x + 3 ir f_{2}(x) = 2x^{2} + 4: f(x) = f_{1}(x) · f_{2}(x). Aišku, kad polinomo f(x) koeficientai neviršys polinomu_{‘} f_{1}(x) ir f_{2}(x) maksimaliu_{‘} koeficientu_{‘} sandaugos. O ji yra 4 · 7 = 28. Tegu m = 7 · 5 > 28.

Kai m_{1} = 5, tai res_{5}(x) = r_{5}(7x + 3) · r_{5}(2x^{2} + 4) = (2x + 3)(2x^{2} + 4) = 4x^{3} + x^{2} + 3x + 2.

Kai m_{2} = 7, tai

res_{7}(x) = r_{7}(7x + 3) · r_{7}(2x^{2} + 4) = 3 · (2x^{2} + 4) = 6x^{2} + 5. Dabar turėtume spre_{‘}sti šia_{‘} lyginiu_{‘} sistema_{‘}:

res(x) ≡ 4x^{3} + x^{2} + 3x + 2 (mod 5),

res(x) ≡ 6x^{2} + 5 (mod 7).

Aišku, kad res(x) = ax^{3} + bx^{2} + cx + d. Šio polinomo koeficientus rasime išsprende_{‘} lyginiu_{‘} sistemas:

a ≡ 4 (mod 5), b ≡ 1 (mod 5), c ≡ 3 (mod 5), d ≡ 2 (mod 5), a ≡ 0 (mod 7), b ≡ 6 (mod 7), c ≡ 0 (mod 7), d ≡ 5 (mod 7). Pritaike_{‘} 4 kartus 6.29 algoritma_{‘}, gausime

a = 14, b = 6, c = 28, d = 12, t.y. f(x) = 14x^{3} + 6x^{2} + 28x + 12.

Pastebėsime, kad sprendžiant lyginiu_{‘} sistema_{‘}

res(x) ≡ res_{m_{j}}(x) (mod m_{j}), 1 ⩽ j ⩽ l,

buvo pasinaudota teiginiu: jeigu u(x) = a_{n}x^{n} + … + a_{0} ir v(x) = b_{n}x^{n} + … + b_{0} polinomai iš Z[x], o m ∈ N, tai

u(x) ≡ v(x) (mod m) ⟺ u(x) − v(x) dalijasi iš m ⟺ (a_{i} − b_{i}) dalijasi iš m, 1 ⩽ i ⩽ n ⟺ a_{i} ≡ b_{i} (mod m), 1 ⩽ i ⩽ n.