Квантор, предикаттай гаргалгааны дүрмүүд
Лекц 14
Read more...
Tuesday, April 27, 2010
Monday, April 19, 2010
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 бий.
Read more...
Алгоритмын схем:
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 бий.
Read more...
Sunday, April 18, 2010
MT116 хичээлийн явцын шалгалт 2
Явцын шалгалтыг 13-р долоо хоногын лекцийн цаг дээр авна.
4 сарын 21, Лхагва гариг, 8.00
205-д.
Read more...
4 сарын 21, Лхагва гариг, 8.00
205-д.
Read more...
Monday, April 5, 2010
SA 200 хичээлийн лаб 4
Дараах 2 ажлыг хийж шалгуулна уу.
1. Фермагийн теоремыг ашиглаж 3^201 mod 11-г ол. (Үүнд: 3^201-нь гурвын 201 зэрэг юм.)
2. Оюутан бүр өөрийн оюутны кодноос n гэсэн тоог дараах байдлаар гаргаж авна.
Хэрэв таны оюутны кодын сүүлийн 3 цифр болох abc тоо сондгой бол n=abc,
тэгш бол n=abc+1.
Оюутан бүр өөрийн n тоог Miller-Rabin-ий тестээр шалгаж анхны тоо эсэхийг тогтооно.
Тестийг нэг удаа биш a-ийн хэд хэдэн утганд хийж харгалзах магадлалыг ихэсгэ.
Жишээлбэл. SW08D232 кодноос n=232+1=233 гэсэн тоо үүснэ.
Read more...
1. Фермагийн теоремыг ашиглаж 3^201 mod 11-г ол. (Үүнд: 3^201-нь гурвын 201 зэрэг юм.)
2. Оюутан бүр өөрийн оюутны кодноос n гэсэн тоог дараах байдлаар гаргаж авна.
Хэрэв таны оюутны кодын сүүлийн 3 цифр болох abc тоо сондгой бол n=abc,
тэгш бол n=abc+1.
Оюутан бүр өөрийн n тоог Miller-Rabin-ий тестээр шалгаж анхны тоо эсэхийг тогтооно.
Тестийг нэг удаа биш a-ийн хэд хэдэн утганд хийж харгалзах магадлалыг ихэсгэ.
Жишээлбэл. SW08D232 кодноос n=232+1=233 гэсэн тоо үүснэ.
Read more...
Sunday, March 14, 2010
SA200 хичээлийн явц дундын шалгалт 1
Шалгалтыг 20-ны (Бямба гариг)-т 12 цагаас 206-д авна.
Read more...
Read more...
MT116 хичээлийн явцын шалгалт 1
Явц дундын шалгалт авах тухай
7-р долоо хоног хүртэл үзсэн сэдвүүдээр шалгалт авна.
3-р сарын 20-нд (Бямба гариг) 10 цагаас 130, 206 өрөөнүүдэд.
Read more...
7-р долоо хоног хүртэл үзсэн сэдвүүдээр шалгалт авна.
3-р сарын 20-нд (Бямба гариг) 10 цагаас 130, 206 өрөөнүүдэд.
Read more...
Thursday, March 11, 2010
SA200 хичээлийн лаб 3
Хялбаршуулсан AES-ийг гараар туршиж үзнэ.
Сурах бичгийн 5-р бүлгийн хавсралт 5B-д дэлгэрэнгүй заавар бий.
(Part 1, Chapter 5, Appendix 5B, Simplified AES)
Read more...
Сурах бичгийн 5-р бүлгийн хавсралт 5B-д дэлгэрэнгүй заавар бий.
(Part 1, Chapter 5, Appendix 5B, Simplified AES)
Read more...
Tuesday, February 9, 2010
SA200 хичээлийн лаб 2
Лабораторийн ажил 2-т Data Encryption Standard-ийн хялбаршуулсан хувилбар болох S-DES (Simplified DES)-ийн ажиллах зарчимыг алхам бүрээр шалгаж, гараар бодит жишээн дээр туршиж үзнэ. Боломжтой бол програм бичнэ.
Stallings-ийн хавсралт C-д Хялбаршуулсан DES -г маш тодорхой тайлбарласан байдаг.
Санта Клара их сургуулийн профессор Эдвард Шаефер S-DES-г зохиосон бөгөөд энэ нь нууцлал хамгаалалын алгоритм гэхээсээ илүү сургалтын зориулалттай алгоритм юм. Жинхэнэ DES алгоритмтай адилхан бүтэцтэй боловч маш бага параметрүүдтэй болохоор гараар ажиллаж ойлгоход үнэхээр зохимжтой хувилбар болно. Жишээлбэл : оролтын блок оригиналь DES-т 64 бит байхад S-DES-т 8 бит байна.
Read more...
Stallings-ийн хавсралт C-д Хялбаршуулсан DES -г маш тодорхой тайлбарласан байдаг.
Санта Клара их сургуулийн профессор Эдвард Шаефер S-DES-г зохиосон бөгөөд энэ нь нууцлал хамгаалалын алгоритм гэхээсээ илүү сургалтын зориулалттай алгоритм юм. Жинхэнэ DES алгоритмтай адилхан бүтэцтэй боловч маш бага параметрүүдтэй болохоор гараар ажиллаж ойлгоход үнэхээр зохимжтой хувилбар болно. Жишээлбэл : оролтын блок оригиналь DES-т 64 бит байхад S-DES-т 8 бит байна.
Read more...
МТ116 Лекц 3
Хэллэгийн логикийн үргэлжлэл: Илэрхийлэлийн утга бодох, Буллийн функц, тавтолог, харшил.
Лекц 3
Лекц 3 (үргэлжлэл)
Read more...
Лекц 3
Лекц 3 (үргэлжлэл)
Read more...
МТ116 Лекц 2
Хэллэгийн логикийн үргэлжлэл: Логик үйлдлүүд, үйлдлийн дараалал, логик илэрхийлэл
Лекц 2
Лекц 2 (үргэлжлэл)
Read more...
Лекц 2
Лекц 2 (үргэлжлэл)
Read more...
Subscribe to:
Posts (Atom)