SA200 хичээлийн лаб 5

5-р лабораторийн ажлаар RSA алгоритмыг өөрсдөө ажиллуулж ойлгоно.
Алгоритмын схем:

Key үүсгэх

1. p, q хоорондоо тэнцүү биш хоёр анхны тоо сонгож авна.
2. n=pq, φ(n)=(p-1)(q-1) гэж олно.
3. ХИЕХ(φ(n), e)=1, 1 <e< φ(n) байх e тоог сонгоно. /ө.х φ(n) e хоёр харилцан анхны байхаар e-г сонгож авна.
4. de=1 mod φ(n) байх d тоог сонгоно. /ө.х d нь e-ийн mod φ(n)-аар урвуу элемент.
5. public key = {e, n}
6. private key= {d, n}

Encryption

Plaintext: M<n
Cipher: C=M^e mod n

Decryption

Cipher: C
Plaintext: M=C^d mod n

Тайлбар:

3-р алхамд e тоог сонгохдоо φ(n)-г үржигдэхүүн болгож задлаад тэрхүү үржигдэхүүнд ороогүй эсвэл тэр үржигдэхүүнүүдийн үржигдэхүүн байж чадахгүй тийм тоог сонгож авч болно.
Жишээлбэл : φ(n)=120 байсан гэе.120=2^3 3 5 тул бид e-г 2, 3, 5, аар сонгож авч болохгүйгээс гадна 4, 6, 8, 10, 12, 15, 20, 24, 40, 60 гэх мэт тоогоор сонгож үл болно. (өшөө олон тоо бий)

4-р алхамд e мэдэгдэж байгаа үед de=1 mod φ(n) нөхцөл биелж байхаар d-г олно. Үүнд өргөтгөсөн Евклидийн алгоритмыг ашиглана.

EXTENDED EUCLID(m, b)
1. (A1, A2, A3) ← (1, 0, m); (B1, B2, B3) ← (0, 1, b)
2. if B3 = 0 return A3 = gcd(m, b); no inverse
3. if B3 = 1 return B3 = gcd(m, b); B2 = b^{-1} mod m

4. Q=A3\B3 / A3-г B3-т бүхлээр хуваана.

5. (T1, T2, T3) ← (A1 -QB1, A2 -QB2, A3 -QB3)
6. (A1, A2, A3) ← (B1, B2, B3)
7. (B1, B2, B3) ← (T1, T2, T3)
8. goto 2

Дээрх өргөтгөсөн Евклидийн алгоритм m, b харилцан анхны үед 3-р мөрнөөс
B2 утгаар b-ийн mod m-ээр урвуу элементийг буцаана.
Та бүхэн Stallings номны маань электрон хувилбарт хасах тэмдэг (-) гараагүй байгааг
мэдэж байгаа. Тэхээр номны жишээг ойлгож дагахын тулд маш анхааралтай байна уу.

Жишээлбэл: Өмнөхтэй төстэйгээр φ(n)=120, e=23 гэж үзье. 23 ба 120 харилцан анхны
тул 23-ийн 120 модулиарх урвуу элемент оршин байна. Түүнийг өргөтгөсөн Евклидийн алгоритмаар ольё.



B3=1 тул B2=47 нь 23-ийн 120 модулиарх урвуу элемент болно.
23*47=1081=1 mod 120

p,q-г сонгохдоо хоёр оронтой тоо байхаар сонгохыг зөвлье. Нийт хоёр оронтой анхны тоо 21 бий.