Квантор, предикаттай гаргалгааны дүрмүүд
Лекц 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...
Tuesday, February 2, 2010
SA200 хичээлийн лекц 2
Сурах бичгийн 2-р бүлгийн үлдсэн хэсгийг ярилцаад, 3-р бүлэг рүү орох болно.
3-р бүлгийн слайд :
William Stallings chapter 3
Read more...
3-р бүлгийн слайд :
William Stallings chapter 3
Read more...
Wednesday, January 27, 2010
SA200 хичээлийн лаб 1
1. Цезарийн шифрийн өргөтгөл болох аффин Цезарийн шифр дараах байдлаар тодорхойлогдоно.
Плайнтекст p болгоны хувьд шифртекст c нь c=E(a,b,p)=(ap+b) mod 26 хуулиар хувирна.
Инкрипшн алгоритмийн үндсэн шаардлага нь тухайн хувиргалт нэгэн утгатай байхийг шаарддаг.
Жишээлбэл: хэрэв p, q тэнцүү биш бол E(a,b,p), E(a,b,q) мөн ялгаатай байх ёстой. Хэрэв энэ нөхцөл зөрчигдвөл 2 ялгаатай плайнтекст нэг ижил шифр-т харгалзаж, улмаар дикрипшн хийх боломжгүй болно. Тухайлбал: a=2, b=3 үед E(a,b,0)=E(a,b,13)=3 байна.
2. 2x2 Хилл шифр ашиглаж инкрипшн, дикрипшн хийх программ бич.
3. m хэмжээс бүхий Хилл шифрийг тайлах программ зохио.
Жич: 1-р ажилд a нь 2-той, 13-тай тэнцэж болохгүй, b нь 0, 26 байж болохгүй.
Stallings-iin Chapter 2, Section 2.2-г уншина уу.
Read more...
Плайнтекст p болгоны хувьд шифртекст c нь c=E(a,b,p)=(ap+b) mod 26 хуулиар хувирна.
Инкрипшн алгоритмийн үндсэн шаардлага нь тухайн хувиргалт нэгэн утгатай байхийг шаарддаг.
Жишээлбэл: хэрэв p, q тэнцүү биш бол E(a,b,p), E(a,b,q) мөн ялгаатай байх ёстой. Хэрэв энэ нөхцөл зөрчигдвөл 2 ялгаатай плайнтекст нэг ижил шифр-т харгалзаж, улмаар дикрипшн хийх боломжгүй болно. Тухайлбал: a=2, b=3 үед E(a,b,0)=E(a,b,13)=3 байна.
- b тооны авч болох утганд ямар нэгэн шаардлага бий юу?
- a тооны авч болох утгуудыг тооцоол.
- аффин Цезарийн шифрээр инкрипшн, дикрипшн хийх програм бич.
2. 2x2 Хилл шифр ашиглаж инкрипшн, дикрипшн хийх программ бич.
3. m хэмжээс бүхий Хилл шифрийг тайлах программ зохио.
Жич: 1-р ажилд a нь 2-той, 13-тай тэнцэж болохгүй, b нь 0, 26 байж болохгүй.
Stallings-iin Chapter 2, Section 2.2-г уншина уу.
Read more...
SA200 хичээлийн лекц 1
Эхний лекц сурах бичгийн 1-р бүлгийг товчхон, 2-р бүлгийг дэлгэрэнгүй ярилцах болно.
Лекцийн слайдууд :
William Stallings chapter 1
William Stallings chapter 2
Read more...
Лекцийн слайдууд :
William Stallings chapter 1
William Stallings chapter 2
Read more...
Tuesday, January 26, 2010
SA200 хичээлийн тухай
Энэ хичээл КТМС-ийн хувьд шинээр заагдаж эхэлж байна.
Хичээлийн талаарх мэдээлэл энд бий.
Үндсэн сурах бичиг :
Cryptography and Network Security Principles and Practices, Fourth Edition
By William Stallings
Сурах бичгийн сайт
http://williamstallings.com/Crypto/Crypto4e.html -нд оюутанд зориулсан янз бүрийн мэдээлэлүүд бий.
Сурах бичгийн е-хувилбарыг авах оюутнууд bat120@gmail.com -луу нэр кодтойгоо
мэйл илгээж аваарай.
Read more...
Хичээлийн талаарх мэдээлэл энд бий.
Үндсэн сурах бичиг :
Cryptography and Network Security Principles and Practices, Fourth Edition
By William Stallings
Сурах бичгийн сайт
http://williamstallings.com/Crypto/Crypto4e.html -нд оюутанд зориулсан янз бүрийн мэдээлэлүүд бий.
Сурах бичгийн е-хувилбарыг авах оюутнууд bat120@gmail.com -луу нэр кодтойгоо
мэйл илгээж аваарай.
Read more...
Monday, January 25, 2010
МТ116 хичээлийн бие даалтийн тухай
Бие даалт нийт 41 оноо.
Оюутнууд вариантаа сонгохдоо дараах схемийн дагуу сонгоно.
Номны бүлэг болгон дасгалуудтай ба дасгал болгон вариантуудтай.
Жишээлбэл:
1-р бүлэг 12 дасгалтай, 4-р дасгал 30 варианттай байна.
SW01D017 кодтой оюутан дасгал болгоны 2, 7 -оор төгссөн вариантуудыг сонгоно.
Хоцорсон бие даалтыг дүгнэхгүй!.
Read more...
Оюутнууд вариантаа сонгохдоо дараах схемийн дагуу сонгоно.
Номны бүлэг болгон дасгалуудтай ба дасгал болгон вариантуудтай.
Оюутны кодын төгсгөлийн цифр | Вариантын төгсгөлийн цифр |
1,6 | 1,6 |
2,7 | 2,7 |
3,8 | 3,8 |
4,9 | 4,9 |
5,0 | 5,0 |
Жишээлбэл:
1-р бүлэг 12 дасгалтай, 4-р дасгал 30 варианттай байна.
SW01D017 кодтой оюутан дасгал болгоны 2, 7 -оор төгссөн вариантуудыг сонгоно.
| Сэдэв | 7 хоног | Оноо | Номны бүлэг | Дасгалын дугаар |
|---|---|---|---|---|
1. Хэллэгийн логик сэдвийн бодлого | 3-7 | 10 | 1 | 3-11 |
2. Хэллэгийг томъёолох (Сурах бичгийн 2-р бүлгийг уншиж амаар хамгаалах) | 8 | 5 | 2 | - |
3. Нэмэлт үйлдэл, логикийн үйлдлийг хэрэглэх | 9 | 3 | 3 | 2-5 |
4. Оюун дүгнэлт, түүнийг хүснэгт, Уангийн аргаар шалгах | 10 | 5 | 4 | 3, 8-11 |
5. Оюун дүгнэлтийн гаргалгаа | 11 | 5 | 5 | 1-3 |
6. Теорем батлах | 12 | 3 | 5 | 6 |
7. Предикаттай оюун дүгнэлтийн гаргалгаа | 13 | 5 | 6 | 7-13 |
8. Предикат, түүнийг томъёолох (Сурах бичгийн 7-р бүлгийг уншиж амаар хамгаалах) | 14 | 5 | 8 | - |
Хоцорсон бие даалтыг дүгнэхгүй!.
Read more...
Sunday, January 24, 2010
MT116 хичээлийн тухай.
Математик логик хичээлийг үзэж буй оюутнуудын анхааралд
Үндсэн сурах бичиг :
Математик логик, Ю.Намсрай, Д.Азбаяр, 2006, ШУТИС
(сургуулийн номын санд хангалттай бий)
Нэмэлт материал :
Хэллэгийн логик, предикат логик, гаргалгааны дүрэм сэдвийн хүрээнд ямар ч
нэмэлт материал ашиглаж болно. Интернет болон бусад эх сурвалжуудад маш
их материалууд бий.
70 онооны задаргаа :
Ирц, идэвхи 4 оноо
Үндсэн мэдлэг, чадвар шалгах сэдвийн шалгалт 3 удаа бичгээр
Read more...
Үндсэн сурах бичиг :
Математик логик, Ю.Намсрай, Д.Азбаяр, 2006, ШУТИС
(сургуулийн номын санд хангалттай бий)
Нэмэлт материал :
Хэллэгийн логик, предикат логик, гаргалгааны дүрэм сэдвийн хүрээнд ямар ч
нэмэлт материал ашиглаж болно. Интернет болон бусад эх сурвалжуудад маш
их материалууд бий.
70 онооны задаргаа :
Ирц, идэвхи 4 оноо
Үндсэн мэдлэг, чадвар шалгах сэдвийн шалгалт 3 удаа бичгээр
- Хэллэгийн логикийн үйлдлүүд, логик илэрхийлэл, функц 10 оноо
(VIII долоо хоног) - Оюун дүгнэлт түүний гаргалгаа 10 оноо
(XIII долоо хоног) - Предикатын логик түүний гаргалгаа 5 оноо
(XVI долоо хоног)
Read more...
Subscribe to:
Posts (Atom)