MAT2033 · 8. hafta · cryptography

Kriptografi: Caesar, affine şifre ve RSA

Kaydırma ve affine şifreler, genişletilmiş Öklid ile mod tersi, hızlı modüler üs alma ve küçük asallarla RSA anahtar üretme, şifreleme, çözme. Final konusu.

cryptographyplaintextciphertextshift cipherCaesar cipheraffine ciphermodular inverseextended Euclidean algorithmmodular exponentiationrepeated squaringpublic keyprivate keyRSAEuler's phi function

Bu hafta önceki haftanın (mod, EBOB, Öklid) uygulamasını görüyoruz. Final konusu. Soru tipleri sabit: “encrypt/decrypt with this cipher”, “find the inverse of a mod m”, “compute $a^n \bmod m$ ”, “generate an RSA key, encrypt, decrypt”. Hepsi elle hesap olduğundan küçük sayılarla gelir. Altın kurallar:

Harfler 0’dan başlar: A = 0, Z = 25. A = 1 alırsan bütün cevap kayar.
Her ara adımda mod al. Sayılar hiç büyümesin.
Mod tersi genişletilmiş Öklid ile bulunur ve sonucu çarpıp 1 çıktığını kontrol edersin.
Büyük üs için hızlı üs alma: üssü ikilik tabana yaz, kareleri sırayla al.
RSA’da $d$ , $\varphi(n)$ modunda ters, $n$ modunda değil.

Temel kavramlar

Gizli tutulacak mesaja düz metin (plaintext), şifrelenmiş haline şifreli metin (ciphertext) denir. Şifreleme bir fonksiyon $f$ , çözme onun tersi $f^{-1}$ . Bu yüzden şifreleme fonksiyonu bijection olmalı (hafta 4’teki fonksiyonlar burada geri dönüyor): iki farklı harf aynı harfe gitseydi geri çözemezdin.

Kaydırma şifresi (shift cipher)

$c = f(p) = (p + k) \bmod 26, \qquad p = f^{-1}(c) = (c - k) \bmod 26.$

$k = 3$ olan özel haline Caesar şifresi denir. Örnek: DERS’i Caesar ile şifrele.

D E R S  ->  3  4 17 18
+3       ->  6  7 20 21
         ->  G  H  U  V

Çözerken 3 çıkarırsın. Sonuç negatif olursa 26 ekle: X = 23 için $23 + 3 = 26 \equiv 0$ = A, geri çözerken $0 - 3 = -3 \equiv 23$ = X.

Bu şifre çok zayıf: sadece 26 anahtar var, hepsini denersin. Daha hızlısı frekans analizi (frequency analysis): İngilizce metinde en sık harf E’dir. Şifreli metinde en sık harf H ise büyük ihtimalle $k = 7 - 4 = 3$ . Affine şifrede de aynı fikir çalışır, sadece iki harf eşleşmesinden iki bilinmeyenli ( $a$ ve $b$ ) bir denklem sistemi çözersin.

Affine şifre (affine cipher)

$c = (ap + b) \bmod 26, \qquad \gcd(a, 26) = 1.$

Şart neden var? Çözmek için $a$ ‘yı “bölmen” gerekir, yani mod 26’da $a$ ‘nın tersi $a^{-1}$ lazım. Ters ancak $\gcd(a, 26) = 1$ ise vardır. Çözme:

$p = a^{-1}(c - b) \bmod 26.$

Örnek: $a = 5$ , $b = 8$ ile HI.

H = 7:  5*7 + 8 = 43,  43 mod 26 = 17  -> R
I = 8:  5*8 + 8 = 48,  48 mod 26 = 22  -> W
Sifreli: RW

Çözmek için $5^{-1} \bmod 26$ lazım. $5 \cdot 21 = 105 = 4 \cdot 26 + 1$ , yani $5^{-1} = 21$ .

R = 17:  21 * (17 - 8) = 189,  189 mod 26 = 7   -> H
W = 22:  21 * (22 - 8) = 294,  294 mod 26 = 8   -> I

TUZAK · “5’e böl” yazmak. Mod aritmetiğinde bölme yoktur. $(c - 8)/5$ yazmak yerine $5^{-1} = 21$ ile çarparsın. $9/5$ tam sayı bile değil, ama $21 \cdot 9 \bmod 26$ gayet tam sayı.

Mod tersi (modular inverse)

$\bar{a}$ , $a$ ‘nın mod $m$ tersidir: $a\bar{a} \equiv 1 \pmod m$ .

Teorem. $\gcd(a, m) = 1$ ise $a$ ‘nın mod $m$ ‘de bir tersi vardır.

Proof. Suppose gcd(a, m) = 1. By Bezout's identity there are
integers s and t with  s*a + t*m = 1.
Then s*a = 1 - t*m, so m | (s*a - 1), i.e. s*a ≡ 1 (mod m).
Hence s is an inverse of a modulo m. ∎

Türkçesi: Bezout katsayısını bulursan tersi de bulmuş olursun. Yöntem genişletilmiş Öklid (extended Euclidean algorithm). Örnek: $7^{-1} \bmod 40$ .

40 = 5*7 + 5
 7 = 1*5 + 2
 5 = 2*2 + 1
Geri:  1 = 5 - 2*2
         = 5 - 2*(7 - 5)        = 3*5 - 2*7
         = 3*(40 - 5*7) - 2*7   = 3*40 - 17*7
7 * (-17) ≡ 1 (mod 40)  ->  -17 + 40 = 23
Kontrol: 7 * 23 = 161 = 4*40 + 1

İPUCU · son satırda kontrol. Tersi bulduktan sonra $a \cdot \bar{a} \bmod m$ hesapla. 1 değilse geri yerine koyarken bir işaret kaçmıştır. On saniyelik kontrol, bütün soruyu kurtarır.

Hızlı modüler üs alma (repeated squaring)

$5^{117} \bmod 23$ gibi bir sayıyı 117 kez çarparak hesaplamazsın. Fikir: $117$ ‘yi ikilik tabanda yaz, $5$ ‘in $5^1, 5^2, 5^4, 5^8, \dots$ kuvvetlerini sırayla kare alarak bul, biti 1 olan kuvvetleri çarp. Her adımda mod al.

$117 = 64 + 32 + 16 + 4 + 1 = (1110101)_2$ .

$i$	bit	$5^{2^i} \bmod 23$	çarpım (x)
0	1	5	5
1	0	$25 \equiv 2$	5
2	1	$4$	$5 \cdot 4 = 20$
3	0	$16$	20
4	1	$256 \equiv 3$	$20 \cdot 3 = 60 \equiv 14$
5	1	$9$	$14 \cdot 9 = 126 \equiv 11$
6	1	$81 \equiv 12$	$11 \cdot 12 = 132 \equiv 17$

Sonuç: $5^{117} \bmod 23 = 17$ . 117 çarpma yerine yaklaşık 12 çarpma yaptık. Bu yüzden algoritma $O(\log n)$ çarpma kullanır.

RSA

RSA bir açık anahtarlı (public key) sistemdir: şifreleme anahtarını herkes bilir, çözme anahtarını sadece alıcı bilir.

Anahtar üretme:

İki asal seç: $p$ , $q$ . $n = pq$ .
$\varphi(n) = (p-1)(q-1)$ hesapla.
$\gcd(e, \varphi(n)) = 1$ olan bir $e$ seç.
$d = e^{-1} \bmod \varphi(n)$ bul.
Açık anahtar $(n, e)$ , gizli anahtar $d$ .

Şifreleme ve çözme:

$C = M^e \bmod n, \qquad M = C^d \bmod n.$

Çözümlü örnek

$p = 13$ , $q = 19$ , $e = 5$ , mesaj $M = 42$ .

n = 13 * 19 = 247
phi = 12 * 18 = 216
gcd(5, 216) = 1  -> e = 5 gecerli
d = 5^-1 mod 216:  5 * 173 = 865 = 4*216 + 1  -> d = 173

Sifrele: C = 42^5 mod 247
42^2 = 1764 = 7*247 + 35          -> 35
42^4 = 35^2 = 1225 = 4*247 + 237  -> 237
42^5 = 237 * 42 = 9954 = 40*247 + 74 -> C = 74

Coz: 74^173 mod 247 = 42   (hizli us alma ile)

Neden çalışır? $ed \equiv 1 \pmod{\varphi(n)}$ olduğu için $M^{ed} = M^{1 + k\varphi(n)}$ . Fermat’ın küçük teoremi (Fermat’s little theorem) sayesinde $M^{\varphi(n)}$ çarpanları mod $p$ ve mod $q$ ‘da 1’e çöker, geriye $M$ kalır. Sınavda genelde bu ispat değil, hesap istenir.

Neden güvenli? $d$ ‘yi bulmak için $\varphi(n)$ lazım, onun için $p$ ve $q$ . Küçük $n$ ‘yi çarpanlarına ayırmak kolay, ama gerçek RSA’da $n$ yüzlerce basamaklı ve çarpanlara ayırmak pratikte imkansız.

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
A = 1, B = 2, …	A = 0, …, Z = 25
Affine çözerken $(c - b)/a$	$a^{-1}(c - b) \bmod 26$ , bölme yok
$a = 13$ affine için uygun	$\gcd(13, 26) = 13$ , tersi yok
Mod tersi negatif çıktı, öyle bıraktım	$m$ ekle: $-17 \bmod 40 = 23$
RSA’da $d = e^{-1} \bmod n$	$d = e^{-1} \bmod \varphi(n)$
$\varphi(n) = n - 1$	$n = pq$ için $\varphi(n) = (p-1)(q-1)$
Üs alırken sonda mod al	Her kare ve çarpımdan sonra mod al
Hızlı üs alırken bütün kuvvetleri çarp	Sadece ikilik açılımda biti 1 olanları

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1kolay

Encrypt the message CODE with the Caesar cipher $f(p) = (p + 3) \bmod 26$ (A = 0, ..., Z = 25).

Cevabı göster

FRGH

Harfleri sayıya çevir: C = 2, O = 14, D = 3, E = 4. 3 ekle: 5, 17, 6, 7. Hepsi 26'dan küçük, mod gerekmedi. Harfe çevir: F, R, G, H.

Soru 2kolay

The ciphertext OLSSV was produced by a shift cipher with key $k = 7$ . Decrypt it.

Cevabı göster

HELLO

Çözme $p = (c - 7) \bmod 26$ . O = 14 → 7 = H. L = 11 → 4 = E. S = 18 → 11 = L (iki kez). V = 21 → 14 = O. Sonuç HELLO.

Soru 3orta

Encrypt OK with the affine cipher $f(p) = (7p + 3) \bmod 26$ .

Cevabı göster

O = 14: $7 \cdot 14 + 3 = 101$ , $101 \bmod 26 = 101 - 78 = 23$ → X. K = 10: $7 \cdot 10 + 3 = 73$ , $73 \bmod 26 = 73 - 52 = 21$ → V.

Soru 4orta

Find the inverse of 7 modulo 26.

Cevabı göster

Öklid: $26 = 3 \cdot 7 + 5$ , $7 = 1 \cdot 5 + 2$ , $5 = 2 \cdot 2 + 1$ . Geri yerine koy: $1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3 \cdot 5 - 2 \cdot 7 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3 \cdot 26 - 11 \cdot 7$ . Yani $7 \cdot (-11) \equiv 1$ , $-11 \bmod 26 = 15$ . Kontrol: $7 \cdot 15 = 105 = 4 \cdot 26 + 1$ .

Soru 5orta

Which of $a = 4, 9, 13, 15$ can be used in an affine cipher $f(p) = (ap + b) \bmod 26$ ?

Cevabı göster

9 and 15

Çözülebilmesi için $a$ 'nın mod 26'da tersi olmalı, yani $\gcd(a, 26) = 1$ . $26 = 2 \cdot 13$ . 4 çift ( $\gcd = 2$ ), 13 ise $\gcd = 13$ : ikisi de olmaz. 9 ve 15 ne 2'ye ne 13'e bölünür: geçerli.

Soru 6orta

Use the extended Euclidean algorithm to find $17^{-1} \bmod 60$ .

Cevabı göster

$60 = 3 \cdot 17 + 9$ , $17 = 1 \cdot 9 + 8$ , $9 = 1 \cdot 8 + 1$ . Geri: $1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2(60 - 3 \cdot 17) - 17 = 2 \cdot 60 - 7 \cdot 17$ . Ters $-7 \equiv 53 \pmod{60}$ . Kontrol: $17 \cdot 53 = 901 = 15 \cdot 60 + 1$ .

Soru 7orta

Compute $3^{45} \bmod 7$ .

Cevabı göster

Küçük kuvvetler: $3^1 = 3$ , $3^2 = 2$ , $3^3 = 6$ , $3^6 = 6^2 = 36 \equiv 1 \pmod 7$ . $45 = 6 \cdot 7 + 3$ , yani $3^{45} = (3^6)^7 \cdot 3^3 \equiv 1 \cdot 6 = 6$ .

Soru 8zor

Use repeated squaring to compute $6^{73} \bmod 29$ . Show the binary expansion of the exponent.

Cevabı göster

$73 = (1001001)_2 = 64 + 8 + 1$ . Kareler mod 29: $6^1 = 6$ , $6^2 = 36 \equiv 7$ , $6^4 = 49 \equiv 20$ , $6^8 = 400 \equiv 23$ , $6^{16} = 529 \equiv 7$ , $6^{32} \equiv 20$ , $6^{64} \equiv 23$ . Biti 1 olanları çarp: $6 \cdot 23 \cdot 23$ . $6 \cdot 23 = 138 \equiv 22$ , $22 \cdot 23 = 506 \equiv 13 \pmod{29}$ .

Soru 9orta

In RSA, let $p = 5$ , $q = 11$ and $e = 3$ . Find $n$ , $\varphi(n)$ and the private key $d$ .

Cevabı göster

n = 55, phi(n) = 40, d = 27

$n = 5 \cdot 11 = 55$ , $\varphi(n) = (p-1)(q-1) = 4 \cdot 10 = 40$ . $\gcd(3, 40) = 1$ , ters var. $d = 3^{-1} \bmod 40$ : $3 \cdot 27 = 81 = 2 \cdot 40 + 1$ , yani $d = 27$ .

Soru 10zor

With the RSA key $n = 55$ , $e = 3$ , $d = 27$ , encrypt $M = 8$ . What do you get when you decrypt the result?

Cevabı göster

C = 17; decrypting gives 8

$C = 8^3 \bmod 55 = 512 \bmod 55$ . $55 \cdot 9 = 495$ , $512 - 495 = 17$ . Çözme $17^{27} \bmod 55$ ; hızlı üs alma ile $8$ çıkar, mesaj geri geldi. RSA'nın doğru kurulduğunun kontrolü budur.

Soru 11zor

An RSA public key is $(n, e) = (77, 7)$ . Find $d$ and decrypt the ciphertext $C = 37$ .

Cevabı göster

d = 43, M = 9

$77 = 7 \cdot 11$ , $\varphi = 6 \cdot 10 = 60$ . $d = 7^{-1} \bmod 60$ : $7 \cdot 43 = 301 = 5 \cdot 60 + 1$ , $d = 43$ . Çözme: $37^{43} \bmod 77 = 9$ . Kontrol için ileri yönde şifrele: $9^2 = 81 \equiv 4$ , $9^4 \equiv 16$ , $9^7 = 9^4 \cdot 9^2 \cdot 9 \equiv 16 \cdot 4 \cdot 9 = 576 \equiv 37$ . Tuttu.

Soru 12kolay

Why must the RSA exponent $e$ satisfy $\gcd(e, \varphi(n)) = 1$ ? Illustrate with $\varphi(n) = 40$ , $e = 4$ .

Cevabı göster

Otherwise e has no inverse d mod phi(n), so there is no decryption key.

Gizli anahtar $d$ , $e \cdot d \equiv 1 \pmod{\varphi(n)}$ olacak sayıdır. Bu ters sadece $\gcd(e, \varphi(n)) = 1$ ise vardır. $e = 4$ , $\varphi = 40$ için $\gcd = 4$ : $4d$ her zaman 4'ün katıdır, $40k + 1$ ise tektir, eşit olamaz. $d$ yok, şifre çözülemez.

Doğrulama: Bütün şifreleme/çözme sonuçları harf harf kodla, mod tersleri genişletilmiş Öklid ve kaba kuvvetle iki yoldan, üs alma izleri adım adım ve BigInt ile, RSA anahtarları ve şifre/çözüm node ile hesaplandı; n = 247 anahtarı için bütün M değerlerinde şifrele-çöz döngüsü kontrol edildi (verify/MAT2033/08.mjs).

Deftere not kartı

Harf -> sayi: A=0 ... Z=25, her islem mod 26 Shift: c = (p + k) mod 26, coz: p = (c - k) mod 26 (Caesar: k = 3) Affine: c = (ap + b) mod 26, gcd(a,26)=1 sart; coz: p = a^-1 (c - b) mod 26 Gecerli a: 1,3,5,7,9,11,15,17,19,21,23,25 (cift ve 13 olmaz) a^-1 mod m: Euclid + geri yerine koy -> 1 = s*a + t*m -> a^-1 = s mod m Negatif cikarsa m ekle: -11 mod 26 = 15. Kontrol: a * a^-1 mod m = 1 Hizli us: ussu ikilige cevir, kareleri sirayla al (her adimda mod), biti 1 olanlari carp RSA: p, q asal; n = pq; phi = (p-1)(q-1); gcd(e, phi) = 1; d = e^-1 mod phi Acik anahtar (n, e), gizli d. Sifrele C = M^e mod n, coz M = C^d mod n Guvenlik: n'yi carpanlara ayirmak zor, phi bilinmeden d bulunamaz Kontrol: coz(sifrele(M)) = M olmali