การเข้ารหัส Yaschenko หนังสือ: Yashchenko V.V.

ต่ำกว่าทั้งหมด เอ็ด V.V. Yashchenko บทนำสู่ CRYPTOGRAPHY ผู้แต่ง: V. V. Yashchenko (บรรณาธิการ ตอนที่ 1), N. P. Varnovsky (บทที่ 2, 3), Yu. V. Nesterenko (บทที่ 4), G. A Kabatyansky (บทที่ 5), P. N. Devyanin, V. G. Proskurin, A. V. Cheremushkin (บทที่ 6), P. A. Gyrdymov, A. Yu. Zubov, A. V. Zyazin, V. N Ovchinnikov (บทที่ 7) เป็นครั้งแรกในภาษารัสเซีย หนังสือเล่มนี้ได้นำเสนอการนำเสนออย่างเป็นระบบเกี่ยวกับพื้นฐานทางวิทยาศาสตร์ของการเข้ารหัสตั้งแต่ตัวอย่างที่ง่ายที่สุดและแนวคิดพื้นฐานไปจนถึงการสร้างการเข้ารหัสที่ทันสมัย การทำความเข้าใจหลักการของการเข้ารหัสกลายเป็นสิ่งจำเป็นสำหรับหลาย ๆ คนเนื่องจากการใช้เครื่องมือรักษาความปลอดภัยข้อมูลการเข้ารหัสอย่างแพร่หลาย ดังนั้นหนังสือเล่มนี้จึงมีประโยชน์ต่อผู้อ่านทั่วไป หนังสือเล่มนี้มีไว้สำหรับนักเรียนของคณิตศาสตร์และผู้เชี่ยวชาญด้านความปลอดภัยของข้อมูล สารบัญ คำนำ 5 บทที่ 1 แนวคิดพื้นฐานของการเข้ารหัส 7 1. บทนำ 7 2. เรื่องของการเข้ารหัส 8 3. พื้นฐานทางคณิตศาสตร์ 15 4. ทิศทางใหม่ 18 5. บทสรุป 23 บทที่ 2. ทฤษฎีการเข้ารหัสและความซับซ้อน 25 1. บทนำ 25 2. การเข้ารหัสและการคาดเดา P=/NP 28 3. ฟังก์ชันทางเดียว 30 4. ตัวสร้างแบบสุ่มเทียม 32 5. หลักฐานที่ไม่มีความรู้ 35 บทที่ 3 โปรโตคอลการเข้ารหัส 41 1. บทนำ 41 2. ความซื่อสัตย์ โปรโตคอลการตรวจสอบและ ลายเซนต์อิเล็กทรอนิกส์ 44 3. การตรวจสอบย้อนกลับไม่ได้ เงินอิเล็กทรอนิกส์ 60 4. โปรโตคอลการโยนเหรียญ 67 5. แบ่งปันความลับอีกครั้ง 72 6. มาเล่นลูกเต๋ากันเถอะ ระเบียบวิธีลงคะแนนเสียง 76 7. เหนือกว่าสมมติฐานมาตรฐาน ข้อมูลลับ 81 การส่งต่อข้อความ 8. แทนที่จะเป็นบทสรุป 84 บทที่ 4 ปัญหาอัลกอริทึมในทฤษฎีจำนวน 86 1. บทนำ 86 2. ระบบการเข้ารหัส RSA 88 3. ความซับซ้อนของอัลกอริทึมทฤษฎีจำนวน 91 4. วิธีแยกแยะจำนวนคอมโพสิตจาก จำนวนเฉพาะ 96 5. วิธีสร้างจำนวนเฉพาะจำนวนมาก 99 6. วิธีทดสอบจำนวนเฉพาะที่มีค่ามาก 102 7. วิธีแยกตัวประกอบตัวเลขประกอบ 107 8. ลอการิทึมที่ไม่ต่อเนื่อง 110 9. บทสรุป 115 บทที่ 5. คณิตศาสตร์ของการแบ่งปันความลับ 118 1. บทนำ 118 2. การแบ่งปันความลับสำหรับโครงสร้างการเข้าถึงโดยพลการ 120 3 การแบ่งปันความลับเชิงเส้น 123 4. การแบ่งปันความลับในอุดมคติและเมทรอยด์ 125 บทที่ 6. คอมพิวเตอร์และการเข้ารหัส 130 1. แทนการแนะนำ 130 2. ทฤษฎีบางอย่าง 132 3. จะเข้ารหัสไฟล์ได้อย่างไร? 140 4. มาเรียนรู้จากความผิดพลาดของคนอื่นกันเถอะ 153 5. แทนที่จะเป็นข้อสรุป 163 บทที่ 7 การแข่งขันกีฬาโอลิมปิกในการเข้ารหัสสำหรับเด็กนักเรียน 165 1. บทนำ 166 2. รหัสตัวเลขทดแทน 169 3. รหัสการเรียงสับเปลี่ยน 182 4. รหัสการแทนที่หลายตัวอักษรด้วยรหัสตามระยะ 190 5. เงื่อนไขของปัญหาโอลิมปิกในวิชาคณิตศาสตร์และการเข้ารหัส 198 6. ทิศทางและแนวทางแก้ไข 210 ภาคผนวก: ข้อความที่ตัดตอนมาจากบทความโดย K. Shannon "ทฤษฎีการสื่อสารในระบบลับ" 15 4. ทิศทางใหม่ 18 5. บทสรุป 23 บทที่ 2 ทฤษฎีการเข้ารหัสและความซับซ้อน 25 1. บทนำ 25 2. การเข้ารหัสและการคาดเดา P^NP 28 3. ฟังก์ชันทางเดียว 30 4. ตัวสร้างแบบสุ่มเทียม 32 5. การพิสูจน์ความรู้ที่เป็นศูนย์ 35 บทที่ 3 โปรโตคอลการเข้ารหัส 41 1. บทนำ 41 2 ความซื่อสัตย์. โปรโตคอลการตรวจสอบและลายเซ็นอิเล็กทรอนิกส์ 44 3. การตรวจสอบย้อนกลับ เงินอิเล็กทรอนิกส์ 60 4. โปรโตคอลเช่น "โยนเหรียญทางโทรศัพท์" ... 67 5. อีกครั้งเกี่ยวกับการแบ่งปันความลับ 72 6. มาเล่น "ลูกเต๋า" กันเถอะ ระเบียบวิธีลงคะแนนเสียง 76 7. เหนือกว่าสมมติฐานมาตรฐาน ข้อความที่เป็นความลับที่เป็นความลับ 81 8. แทนที่จะเป็นบทสรุป 84 บทที่ 4. ปัญหาอัลกอริทึมในทฤษฎีจำนวน 86 1. บทนำ 86 2. ระบบการเข้ารหัส RSA 88 3. ความซับซ้อนของอัลกอริทึมทฤษฎีจำนวน 91 4. วิธีแยกแยะจำนวนคอมโพสิตจาก จำนวนเฉพาะ 96 5. วิธีสร้างจำนวนเฉพาะขนาดใหญ่ 99 6. วิธีทดสอบจำนวนเฉพาะจำนวนมากสำหรับความเป็นเฉพาะ 102 7. วิธีแยกตัวประกอบจำนวนเฉพาะ 107 8 ลอการิทึมแบบไม่ต่อเนื่อง 110 9. บทสรุป 115 บทที่ 5. คณิตศาสตร์ของการแบ่งปันความลับ 118 1. บทนำ 118 2. การแบ่งปันความลับสำหรับโครงสร้างการเข้าถึงโดยพลการ . 120 3. การแบ่งปันความลับเชิงเส้น 123 4. การแบ่งปันความลับในอุดมคติและเมทรอยด์ 125 บทที่ 6. คอมพิวเตอร์และการเข้ารหัส 130 1. แทนที่จะเป็นการแนะนำ 130 2. ทฤษฎีบางอย่าง 132 3. วิธีการเข้ารหัสไฟล์? 140 4. มาเรียนรู้จากความผิดพลาดของคนอื่นกันเถอะ 153 5. แทนที่จะเป็นข้อสรุป 163 บทที่ 7 การแข่งขันกีฬาโอลิมปิกในการเข้ารหัสสำหรับเด็กนักเรียน 165 1. บทนำ 166 2. รหัสตัวเลขทดแทน 169 3. รหัสการเรียงสับเปลี่ยน 182 4. รหัสการแทนที่หลายตัวอักษรด้วยรหัสตามระยะ 190 5. เงื่อนไขของปัญหาโอลิมปิกในวิชาคณิตศาสตร์และการเข้ารหัส . 198 6. ทิศทางและการตัดสินใจ 210 ภาคผนวก: ข้อความที่ตัดตอนมาจากบทความโดย K. Shannon “ทฤษฎีการสื่อสารในระบบลับ” 235 คำนำของฉบับพิมพ์ครั้งที่สอง ฉบับพิมพ์ครั้งที่สองนี้แก้ไขข้อผิดพลาดในการพิมพ์และความไม่ถูกต้องที่สังเกตเห็นในฉบับพิมพ์ครั้งแรก กันยายน 2542 V. Yashchenko คำนำของ Cryptography ฉบับพิมพ์ครั้งแรก - ศาสตร์แห่งการเข้ารหัส - ได้รับการจัดประเภทมาเป็นเวลานานเนื่องจากใช้เป็นหลักในการปกป้องความลับของรัฐและการทหาร ปัจจุบันมีการใช้วิธีการและวิธีการเข้ารหัสเพื่อรับรองความปลอดภัยของข้อมูลไม่เพียง แต่ของรัฐเท่านั้น แต่ยังรวมถึงบุคคลและองค์กรด้วย นี้ไม่จำเป็นต้องเป็นเรื่องของความลับ ข้อมูลมากเกินไปคือการ "เดิน" ไปทั่วโลกในรูปแบบดิจิทัล และเหนือข้อมูลนี้มีภัยคุกคามจากการรู้จักที่ไม่เป็นมิตร การสะสม การทดแทน การปลอมแปลง ฯลฯ เป็นการเข้ารหัสที่ให้วิธีการที่เชื่อถือได้มากที่สุดในการป้องกันภัยคุกคามดังกล่าว จนถึงตอนนี้ อัลกอริธึมการเข้ารหัสสำหรับผู้บริโภคทั่วไปเป็นความลับโดยมีตราประทับเจ็ดดวง แม้ว่าหลายคนเคยใช้เครื่องมือเข้ารหัสลับบางอย่างแล้ว: การเข้ารหัสอีเมล บัตรธนาคารอัจฉริยะ ฯลฯ โดยธรรมชาติแล้ว คำถามหลักสำหรับผู้ใช้ก็คือว่าเครื่องมือเข้ารหัสลับนี้มีให้หรือไม่ การป้องกันที่เชื่อถือได้ แต่ถึงแม้จะกำหนดคำถามเบื้องต้นนี้อย่างถูกต้อง แต่ก็ไม่ใช่เรื่องง่าย เรากำลังป้องกันศัตรูตัวใดอยู่? อะไรคือความเป็นไปได้ของศัตรูตัวนี้? เขาสามารถบรรลุเป้าหมายอะไรได้บ้าง? จะวัดความน่าเชื่อถือของการป้องกันได้อย่างไร? รายการคำถามดังกล่าวสามารถดำเนินการต่อได้ ในการตอบคำถาม ผู้ใช้ต้องการความรู้เกี่ยวกับแนวคิดพื้นฐานของการเข้ารหัส การนำเสนอที่เป็นที่นิยมของพื้นฐานทางวิทยาศาสตร์ของการเข้ารหัส (เรากำลังพูดถึงเฉพาะการเข้ารหัส "ที่ไม่ใช่ของรัฐ" ส่วนของการเข้ารหัสที่เกี่ยวข้องกับความมั่นคงของรัฐควรเป็นความลับ) เป็นเป้าหมายของหนังสือเล่มนี้ ยังสามารถใช้เป็นสื่อการสอนได้อีกด้วย ยังไม่มีหนังสือที่คล้ายกันในภาษารัสเซีย เนื้อหาของบทจำนวนหนึ่งเผยแพร่โดยผู้เขียนก่อนหน้านี้ในสิ่งพิมพ์อื่น ๆ (บทที่ 1 - ในหนังสือโดย S. A. Dorichenko, V. V. Yashchenko, "25 Studies on ciphers", M.: TEIS, 1994; ตอนที่ 1,2,4 , 5 - ในวารสาร "Mathematical Education", ชุดที่สาม, ฉบับที่ 2, M .: MTsNMO, 1998; บทที่ 7 - ในหนังสือพิมพ์ "Informatics" (ภาคผนวกรายสัปดาห์ของหนังสือพิมพ์ "Pervoe september") ฉบับที่ 4 มกราคม พ.ศ. 2541) ในการเตรียมฉบับนี้ เอกสารเหล่านี้ได้รับการแก้ไขและเพิ่มเติม การนำเสนอเนื้อหาได้รับการออกแบบสำหรับผู้อ่านที่มีความคิดทางคณิตศาสตร์ โดยส่วนใหญ่แล้ว บทต่างๆ จะเป็นอิสระจากกัน (สามารถทำได้ผ่านการทำซ้ำบางส่วน) และสามารถอ่านได้ในลำดับใดก็ได้ บทที่ 1 - เกริ่นนำ - แนะนำให้ทุกคนอ่าน เนื่องจากได้อธิบายแนวคิดพื้นฐานทั้งหมดของการเข้ารหัสลับที่ทันสมัยในระดับที่นิยม: รหัส คีย์ ความปลอดภัย ลายเซ็นดิจิทัลอิเล็กทรอนิกส์ โปรโตคอลการเข้ารหัสลับ ฯลฯ ในบทอื่น ๆ ส่วนหนึ่งของวัสดุซ้ำแล้วซ้ำอีก แต่มีความลึกมากขึ้นแล้ว บทที่ 2, 3, 4, 5 ใช้ข้อมูลบางส่วนจากคณิตศาสตร์ชั้นสูงที่นักเรียนในชั้นเรียนคณิตศาสตร์และนักเรียนรู้จัก บทที่ 6 มุ่งเป้าไปที่นักเลง เทคโนโลยีคอมพิวเตอร์. บทที่ 7 มีเนื้อหาสำหรับการเข้ารหัสโอลิมปิกสำหรับเด็กนักเรียนดังนั้นจึงไม่จำเป็นต้องอ่านความรู้นอกเหนือจากหลักสูตรของโรงเรียน คำเตือน: เครื่องมือเข้ารหัสและผลิตภัณฑ์ซอฟต์แวร์ที่กล่าวถึงในหนังสือเล่มนี้ใช้เพื่อแสดงแนวคิดทั่วไปเกี่ยวกับการเข้ารหัสเท่านั้น ผู้เขียนไม่ได้ตั้งเป้าที่จะประเมินหรือเปรียบเทียบเครื่องมือเข้ารหัสที่มีอยู่ในตลาด การเข้ารหัสถูกวางบนพื้นฐานทางวิทยาศาสตร์ส่วนใหญ่มาจากการทำงานของนักวิทยาศาสตร์ชาวอเมริกันที่โดดเด่น Claude Shannon รายงานของเขาเรื่อง "Mathematical Theory of Cryptography" จัดทำขึ้นในรูปแบบความลับในปี 1945 แยกประเภทและตีพิมพ์ในปี 1948 แปลเป็นภาษารัสเซียในปี 1963 เนื่องจาก "Works on Information Theory and Cybernetics" A963) K. Shannon ได้กลายเป็นหนังสือที่หายากในบรรณานุกรม เรา ได้รวมอยู่ในภาคผนวกส่วนหลักของบทความโดย K. Shannon "ทฤษฎีการสื่อสารในระบบลับ" ขอแนะนำให้อ่านงานน้ำเชื้อนี้สำหรับผู้ที่สนใจในการเข้ารหัส เพื่อความเข้าใจอย่างมืออาชีพเกี่ยวกับอัลกอริธึมการเข้ารหัสและความสามารถในการประเมินจุดแข็งและ ด้านที่อ่อนแอ จำเป็นต้องมีการฝึกอบรมทางคณิตศาสตร์อย่างจริงจังอยู่แล้ว (ในระดับแผนกคณิตศาสตร์ของมหาวิทยาลัย) เนื่องจากวิทยาการเข้ารหัสลับสมัยใหม่มีพื้นฐานมาจากผลลัพธ์เชิงลึกของสาขาคณิตศาสตร์ เช่น ทฤษฎีความซับซ้อนของการคำนวณ ทฤษฎีจำนวน พีชคณิต ทฤษฎีสารสนเทศ ฯลฯ ผู้ที่ต้องการศึกษาการเข้ารหัสอย่างจริงจังสามารถแนะนำเอกสารทบทวนได้ “ การเข้ารหัสในการธนาคาร” โดย Anokhin M. และ. Varnovsky N. P. , Sidelnikova V. M. , Yashchenko V. V. , M.: MEPhI, 1997. ตุลาคม 1998 V. Yashchenko บทที่ 1 แนวคิดพื้นฐานของการเข้ารหัส 1. บทนำ วิธีการถ่ายโอนข้อมูลที่จำเป็นไปยัง ผู้รับที่ต้องการในที่ลับจากผู้อื่น? ผู้อ่านแต่ละคนในช่วงเวลาที่แตกต่างกันและมีเป้าหมายที่แตกต่างกันอาจพยายามแก้ปัญหาในทางปฏิบัตินี้ด้วยตนเอง (เพื่อความสะดวกในการอ้างอิงเพิ่มเติม เราจะเรียกสิ่งนี้ว่า "ปัญหา TP" นั่นคือปัญหาของการส่งข้อมูลลับ) เมื่อเลือกวิธีแก้ปัญหาที่เหมาะสมแล้ว เขามักจะคิดค้นวิธีการส่งข้อมูลอย่างลับๆ ซ้ำๆ ซึ่งมีอายุมากกว่าหนึ่งพันปี เมื่อพิจารณาถึงปัญหา TP แล้ว ไม่ยากเลยที่จะสรุปว่ามีความเป็นไปได้สามประการ 1. สร้างช่องทางการสื่อสารที่เชื่อถือได้อย่างแท้จริงระหว่างสมาชิกซึ่งไม่สามารถเข้าถึงได้สำหรับผู้อื่น 2. ใช้ช่องทางการสื่อสารสาธารณะ แต่ปิดบังความจริงของการถ่ายโอนข้อมูล 3. ใช้ช่องทางการสื่อสารสาธารณะ แต่ส่งข้อมูลที่จำเป็นผ่านช่องทางดังกล่าวในรูปแบบที่เปลี่ยนแปลงซึ่งมีเพียงผู้รับเท่านั้นที่สามารถกู้คืนได้ ให้ความเห็นเกี่ยวกับความเป็นไปได้ทั้งสามนี้ 1. ด้วยระดับการพัฒนาวิทยาศาสตร์และเทคโนโลยีในปัจจุบัน แทบจะเป็นไปไม่ได้เลยที่จะสร้างช่องทางการสื่อสารระหว่างสมาชิกระยะไกลสำหรับการส่งข้อมูลจำนวนมากซ้ำๆ 2. Steganography มีส่วนร่วมในการพัฒนาวิธีการและวิธีการในการซ่อนความจริงของการส่งข้อความ ร่องรอยแรกของวิธีการสเตกาโนกราฟีสูญหายไปในสมัยโบราณ ตัวอย่างเช่นรู้จักวิธีการซ่อนข้อความที่เป็นลายลักษณ์อักษร: โกนศีรษะของทาสเขียนข้อความบนหนังศีรษะและหลังจากที่ผมงอกขึ้นใหม่ทาสก็ถูกส่งไปยังผู้รับ จากงานนักสืบ วิธีการเขียนลับต่างๆ ระหว่างบรรทัดของข้อความธรรมดาที่ไม่มีการป้องกันเป็นที่รู้จักกันดี ตั้งแต่นมไปจนถึงสารเคมีที่ซับซ้อนพร้อมการประมวลผลที่ตามมา วิธีการ "ไมโครดอท" เป็นที่รู้จักจากนักสืบเช่นกัน: ข้อความถูกบันทึกโดยใช้เทคโนโลยีสมัยใหม่บนสื่อขนาดเล็กมาก (ไมโครดอท) ซึ่งส่งด้วยจดหมายธรรมดาเช่นภายใต้ตราประทับหรือที่อื่น ๆ ที่กำหนดไว้ล่วงหน้า ในปัจจุบัน เนื่องจากการใช้คอมพิวเตอร์อย่างแพร่หลาย จึงมีวิธี "ซ่อน" ข้อมูลที่ได้รับการป้องกันไว้ภายในข้อมูลจำนวนมากที่จัดเก็บไว้ในคอมพิวเตอร์อย่างละเอียดหลายวิธี ตัวอย่างภาพของการซ่อนไฟล์ข้อความในไฟล์กราฟิกสามารถพบได้บนอินเทอร์เน็ต1" มันยังได้รับในนิตยสาร Computerra ฉบับที่ 48 B25) ลงวันที่ 1 ธันวาคม 1997 ในหน้า 62 (ควรสังเกตว่า ผู้เขียนบทความใน Steganography ถูกเข้าใจผิดว่าเป็นวิทยาการเข้ารหัสลับในนิตยสาร แน่นอนว่าด้วยความช่วยเหลือของ Steganography เป็นไปได้ที่จะซ่อนข้อความที่เข้ารหัสไว้ล่วงหน้า แต่โดยทั่วไปแล้ว Steganography และ Cryptography นั้นเป็นพื้นที่ที่แตกต่างกันโดยพื้นฐานในทฤษฎีและ การปฏิบัติเพื่อความปลอดภัยของข้อมูล) 3. การพัฒนาวิธีการแปลงข้อมูล (เข้ารหัส) เพื่อป้องกันข้อมูลดังกล่าวจากผู้ใช้ที่ผิดกฎหมาย การเข้ารหัสลับ มีส่วนเกี่ยวข้อง วิธีการและวิธีการในการแปลงข้อมูลดังกล่าวเรียกว่า การเข้ารหัส การเข้ารหัส (encryption) คือ กระบวนการของการใช้รหัสลับกับข้อมูลที่ได้รับการคุ้มครอง เช่น การแปลงข้อมูลที่ได้รับการป้องกัน (ข้อความธรรมดา) เป็นข้อความที่เข้ารหัส (ข้อความเข้ารหัส การเข้ารหัสลับ) โดยใช้กฎเกณฑ์บางอย่างที่มีอยู่ในตัวเลข การถอดรหัสเป็นกระบวนการย้อนกลับของ การเข้ารหัส กล่าวคือ การแปลงข้อความที่เข้ารหัสเป็นข้อมูลที่ได้รับการป้องกันโดยใช้กฎเกณฑ์บางอย่างที่มีอยู่ในรหัส การเข้ารหัสเป็นวิทยาศาสตร์ประยุกต์ มันใช้ความสำเร็จล่าสุดของวิทยาศาสตร์พื้นฐานและประการแรกคือคณิตศาสตร์ ในทางกลับกัน งานเฉพาะทั้งหมดของการเข้ารหัสนั้นขึ้นอยู่กับระดับของการพัฒนาเทคโนโลยีและเทคโนโลยีเป็นหลัก โดยขึ้นอยู่กับวิธีการสื่อสารและวิธีการถ่ายโอนข้อมูลที่ใช้ 2. เรื่องของการเข้ารหัส เรื่องของการเข้ารหัสคืออะไร? เพื่อตอบคำถามนี้ ให้เรากลับไปที่ปัญหา TP เพื่อชี้แจงสถานการณ์และแนวคิดที่ใช้ ก่อนอื่น เราทราบว่าปัญหานี้เกิดขึ้นเฉพาะกับข้อมูลที่ต้องได้รับการปกป้องเท่านั้น โดยปกติในกรณีดังกล่าว พวกเขากล่าวว่าข้อมูลมีความลับหรือได้รับการคุ้มครอง เป็นส่วนตัว เป็นความลับ เป็นความลับ สำหรับสถานการณ์ทั่วไปที่พบได้บ่อยในประเภทนี้ แม้แต่แนวคิดพิเศษก็ได้รับการแนะนำ: - ความลับของรัฐ; - ความลับทางการทหาร ://www.geocities.com/SiliconValley/Vista/6001/ แนวคิดพื้นฐานของการเข้ารหัส - ความลับทางการค้า - ความลับทางกฎหมาย - ความลับทางการแพทย์ ฯลฯ นอกจากนี้ เราจะพูดถึงข้อมูลที่ได้รับการคุ้มครอง โดยคำนึงถึงคุณลักษณะต่อไปนี้ของข้อมูลดังกล่าว: - มีกลุ่มผู้ใช้ที่ถูกต้องตามกฎหมายที่มีสิทธิ์เป็นเจ้าของข้อมูลนี้ - มีผู้ใช้ที่ผิดกฎหมายที่ต้องการรับข้อมูลนี้เพื่อนำไปใช้เพื่อประโยชน์ของตนเองและเพื่อความเสียหายต่อผู้ใช้ที่ถูกต้องตามกฎหมาย เพื่อความง่าย ก่อนอื่นเราจะจำกัดตัวเองให้พิจารณาภัยคุกคามเดียวเท่านั้น - ภัยคุกคามจากการเปิดเผยข้อมูล มีภัยคุกคามอื่น ๆ ต่อข้อมูลที่ได้รับการคุ้มครองจากผู้ใช้ที่ผิดกฎหมาย: การแทนที่ การเลียนแบบ ฯลฯ เราจะพูดถึงพวกเขาด้านล่าง ตอนนี้เราสามารถพรรณนาสถานการณ์ที่ปัญหา TP เกิดขึ้นได้ด้วยแผนภาพต่อไปนี้ (ดูรูปที่ 1) แต่< т >รูปบีพี 1. ที่นี่ A และ B เป็นผู้ใช้ระยะไกลที่ถูกต้องตามกฎหมายของข้อมูลที่ได้รับการคุ้มครอง พวกเขาต้องการแลกเปลี่ยนข้อมูลผ่านช่องทางการสื่อสารสาธารณะ P - ผู้ใช้ที่ผิดกฎหมาย (ฝ่ายตรงข้าม) ที่สามารถสกัดกั้นข้อความที่ส่งผ่านช่องทางการสื่อสารและพยายามดึงข้อมูลที่น่าสนใจจากพวกเขา แบบแผนนี้ถือเป็นแบบอย่างได้ สถานการณ์ปกติ ซึ่งใช้วิธีการเข้ารหัสในการปกป้องข้อมูล ควรสังเกตว่าคำศัพท์ทางการทหารบางคำ (ศัตรู การจู่โจมรหัส ฯลฯ) ได้ฝังรากลึกในอดีตในการเข้ารหัส ซึ่งสะท้อนความหมายของแนวคิดการเข้ารหัสที่สอดคล้องกันได้แม่นยำที่สุด ในเวลาเดียวกัน คำศัพท์ทางการทหารที่รู้จักกันอย่างกว้างขวางตามแนวคิดของรหัส (รหัสกองทัพเรือ รหัสของเจ้าหน้าที่ทั่วไป หนังสือรหัส การกำหนดรหัส ฯลฯ) จะไม่ใช้ในการเข้ารหัสเชิงทฤษฎีอีกต่อไป ความจริงก็คือในช่วงหลายทศวรรษที่ผ่านมา ทฤษฎีการเข้ารหัสได้ก่อตัวขึ้น ซึ่งเป็นทิศทางทางวิทยาศาสตร์ขนาดใหญ่ที่พัฒนาและศึกษาวิธีการในการปกป้องข้อมูลจากการบิดเบือนแบบสุ่มในช่องทางการสื่อสาร และหากก่อนหน้านี้มีการใช้คำว่าการเข้ารหัสและการเข้ารหัสเป็นคำพ้องความหมาย ตอนนี้สิ่งนี้ไม่เป็นที่ยอมรับ ตัวอย่างเช่น นิพจน์ทั่วไป "การเข้ารหัสคือการเข้ารหัสชนิดหนึ่ง" กลายเป็นเรื่องที่ไม่ถูกต้อง การเข้ารหัสเกี่ยวข้องกับวิธีการแปลงข้อมูลที่จะไม่อนุญาตให้ฝ่ายตรงข้ามดึงข้อมูลออกจากข้อความที่สกัดกั้น ในกรณีนี้ ข้อมูลที่ได้รับการคุ้มครองจะไม่ถูกส่งผ่านช่องทางการสื่อสารอีกต่อไป แต่ผลลัพธ์ของการเปลี่ยนแปลงด้วยความช่วยเหลือของรหัสลับ และฝ่ายตรงข้ามต้องเผชิญกับงานยากในการทำลายรหัส การเปิด (แคร็ก) การเข้ารหัสเป็นกระบวนการในการรับข้อมูลที่ได้รับการป้องกันจากข้อความที่เข้ารหัสโดยไม่ทราบรหัสที่ใช้ อย่างไรก็ตาม นอกเหนือจากการสกัดกั้นและเปิดรหัสลับแล้ว ปฏิปักษ์อาจพยายามรับข้อมูลที่ได้รับการคุ้มครองด้วยวิธีอื่นๆ มากมาย วิธีการที่รู้จักกันดีที่สุดคือวิธีการปกปิด เมื่อศัตรูชักชวนให้ผู้ใช้ที่ถูกต้องตามกฎหมายให้ร่วมมือในทางใดทางหนึ่ง และด้วยความช่วยเหลือของตัวแทนนี้ จะได้รับการเข้าถึงข้อมูลที่ได้รับการคุ้มครอง ในสถานการณ์เช่นนี้ การเข้ารหัสไม่มีอำนาจ ปฏิปักษ์อาจพยายามไม่รับ แต่เพื่อทำลายหรือแก้ไขข้อมูลที่ได้รับการคุ้มครองในระหว่างการส่ง นี่เป็นภัยคุกคามต่อข้อมูลประเภทอื่นมากกว่าการดักฟังและทำลายรหัส เพื่อป้องกันภัยคุกคามดังกล่าว มีการพัฒนาวิธีการเฉพาะของตนเอง ดังนั้นระหว่างทางจากผู้ใช้ที่ถูกต้องตามกฎหมายหนึ่งไปยังอีกรายหนึ่ง ข้อมูลจะต้องได้รับการปกป้องในรูปแบบต่างๆ ต่อต้านการคุกคามต่างๆ มีสถานการณ์ของการเชื่อมโยงที่แตกต่างกันซึ่งปกป้องข้อมูล โดยธรรมชาติแล้ว ศัตรูจะพยายามค้นหาจุดอ่อนที่สุดเพื่อเข้าถึงข้อมูลด้วยต้นทุนที่ต่ำที่สุด ซึ่งหมายความว่าผู้ใช้ที่ถูกกฎหมายควรคำนึงถึงสถานการณ์นี้ในกลยุทธ์การป้องกันด้วย: ไม่มีเหตุผลที่จะต้องสร้างลิงก์ที่แข็งแกร่งมากหากมีลิงก์ที่อ่อนแอกว่าอย่างเห็นได้ชัด ("หลักการของการป้องกันที่เท่าเทียมกัน") เราไม่ควรลืมปัญหาสำคัญอีกประการหนึ่ง: ปัญหาอัตราส่วนของราคาข้อมูล ค่าใช้จ่ายในการปกป้องข้อมูล และค่าใช้จ่ายในการได้มา ด้วยระดับการพัฒนาทางเทคโนโลยีในปัจจุบัน วิธีการสื่อสารด้วยตนเอง ตลอดจนการพัฒนาวิธีการสกัดกั้นข้อมูลจากพวกเขา และวิธีการในการปกป้องข้อมูล ต้องใช้ต้นทุนที่สูงมาก ก่อนปกป้องข้อมูล ให้ถามตัวเองสองคำถาม: 1) มีค่าสำหรับคู่ต่อสู้มากกว่าต้นทุนของการโจมตีหรือไม่; 2) มีค่าสำหรับคุณมากกว่าค่าคุ้มครองหรือไม่ ข้อควรพิจารณาเหล่านี้เป็นตัวชี้ขาดเมื่อเลือกวิธีการป้องกันที่เหมาะสม: ทางกายภาพ สเตกาโนกราฟิก การเข้ารหัส ฯลฯ เป็นการสะดวกที่จะอธิบายแนวคิดบางอย่างของการเข้ารหัสด้วยตัวอย่างทางประวัติศาสตร์ ดังนั้นเราจะทำการพูดนอกเรื่องทางประวัติศาสตร์เล็กน้อย เป็นเวลานานที่วิทยาการเข้ารหัสลับเป็นคนนอกรีตเพียงคนเดียว ในหมู่พวกเขามีนักวิทยาศาสตร์ที่มีพรสวรรค์ นักการทูต นักบวช มีหลายกรณีที่การเข้ารหัสถือเป็นมนต์ดำ ช่วงเวลาของการพัฒนาการเข้ารหัสในฐานะศิลปะนี้กินเวลานานหลายชั่วอายุคนจนถึงต้นศตวรรษที่ 20 เมื่อเครื่องเข้ารหัสเครื่องแรกปรากฏขึ้น ความเข้าใจเกี่ยวกับธรรมชาติทางคณิตศาสตร์ของปัญหาที่แก้ไขโดยการเข้ารหัสนั้นเกิดขึ้นในช่วงกลางศตวรรษที่ 20 เท่านั้น - หลังจากผลงานของนักวิทยาศาสตร์ชาวอเมริกันชื่อ C. Shannon ประวัติความเป็นมาของการเข้ารหัสมีความเกี่ยวข้องกับความลับทางการทูตและการทหารจำนวนมาก ดังนั้นจึงถูกปกคลุมไปด้วยหมอกแห่งตำนาน หนังสือที่สมบูรณ์ที่สุดเกี่ยวกับประวัติศาสตร์ของการเข้ารหัสมีมากกว่าหนึ่งพันหน้า มันถูกตีพิมพ์ในปี 1967 และยังไม่ได้แปลเป็นภาษารัสเซีย1" งานพื้นฐานเกี่ยวกับประวัติศาสตร์การเข้ารหัสในรัสเซียเพิ่งได้รับการตีพิมพ์ในภาษารัสเซีย เกี่ยวกับการใช้ตัวเลขในกิจการทหารมีความเกี่ยวข้องกับชื่อของผู้บัญชาการสปาร์ตัน Lysander ( รหัส "Scitala") ซีซาร์ใช้รหัสในการติดต่อของเขาซึ่งลงไปในประวัติศาสตร์ว่าเป็น "รหัสซีซาร์" ในสมัยกรีกโบราณมีการประดิษฐ์ตัวเลขประเภทหนึ่งซึ่งต่อมากลายเป็นที่รู้จักในนาม "จัตุรัส Politia" หนึ่งในนั้น หนังสือเล่มแรกเกี่ยวกับการเข้ารหัสเขียนโดย Abbot I. Tritelius A462-1516) ซึ่งอาศัยอยู่ในเยอรมนี ในปี ค.ศ. 1566 นักคณิตศาสตร์ชื่อดัง D. Cardano ได้ตีพิมพ์ผลงานอธิบายระบบการเข้ารหัสที่เขาคิดค้น ("Cardano lattice") ฝรั่งเศส XVI จากไป ในประวัติศาสตร์การเข้ารหัสลับของกษัตริย์เฮนรี่ที่ 4 และริเชอลิเยอ "อักษรดิจิทัล" ค.ศ. 1700 ผู้เขียนคือปีเตอร์มหาราช (ตัวอย่างบางส่วนจากหนังสือเล่มนี้มีอยู่ใน flyleaf) ข้อมูลบางอย่างเกี่ยวกับคุณสมบัติของยันต์และการประยุกต์ใช้สามารถพบได้ในนิยาย โดยเฉพาะในการผจญภัย นักสืบ และการทหาร วิธีการเปิดมีอยู่ 2 เรื่องที่รู้จักกันดี: "The Gold Bug" โดย E. Poe และ "The Dancing Men" โดย A. Conan Doyle ให้เราพิจารณาสองตัวอย่างโดยละเอียดยิ่งขึ้น รหัส "Scytalus" ตัวเลขนี้เป็นที่รู้จักตั้งแต่สงคราม Sparta กับเอเธนส์ในวันที่ 5 ศตวรรษก่อนคริสต์ศักราช สำหรับการนำไปใช้นั้นใช้ scytala - แท่งที่มีรูปร่างเหมือนทรงกระบอก เทป papyrus แคบ ๆ (ไม่มีช่องว่างและทับซ้อนกัน) พันรอบขดลวด scytal เพื่อขดแล้วข้อความธรรมดาก็เขียนบนเทปนี้ตาม แกน scytala เทปถูกคลายออกและปรากฏ (สำหรับผู้ที่ไม่ได้ฝึกหัด) ว่าจดหมายบางฉบับเขียนขึ้นอย่างไม่เป็นระเบียบบนริบบิ้นจากนั้นริบบิ้นก็ถูกส่งไปยังผู้รับ ผู้รับใช้ scitala เดียวกันในลักษณะเดียวกันบาดแผล ที่ได้รับ เทปและอ่านข้อความตามแกนของดาบปลายปืน โปรดทราบว่าในรหัสนี้ การแปลงข้อความธรรมดาเป็นข้อความเข้ารหัสประกอบด้วยการเรียงสับเปลี่ยนของตัวอักษรของข้อความธรรมดา เดวิด. ผู้ถอดรหัส เรื่องราวของการเขียนลับ นิวยอร์ก: Macmillan, 1967. 2 "Soboleva T. A. การเข้ารหัสในประวัติศาสตร์ของรัสเซีย (ประวัติของบริการเข้ารหัสลับของรัสเซียใน XVIII - ต้นศตวรรษที่ XX) M. , 1994. "Scitala" เรียกว่าการเรียงสับเปลี่ยน ciphers Caesar cipher รหัสนี้ ใช้การแปลงข้อความธรรมดาต่อไปนี้: ตัวอักษรแต่ละตัวของข้อความธรรมดาจะถูกแทนที่ด้วยตัวอักษรตัวที่สามตามหลังในตัวอักษรซึ่งถือว่าเขียนเป็นวงกลมเช่น หลังจาก อักษรบู้"i" ตามด้วยตัวอักษร "a" โปรดทราบว่าซีซาร์แทนที่จดหมายด้วยตัวอักษรตัวที่สามหลังจากนั้น แต่คุณสามารถแทนที่ตัวอักษรอื่นได้ สิ่งสำคัญคือบุคคลที่ส่งข้อความที่เข้ารหัสลับควรรู้ค่ากะนี้ คลาสของรหัสลับที่รหัสของซีซาร์เรียกว่ารหัสทดแทน จากการนำเสนอครั้งก่อน เห็นได้ชัดว่าการประดิษฐ์ตัวเลขที่ดีนั้นเป็นงานที่ลำบาก ดังนั้นจึงควรเพิ่มอายุการใช้งานของการเข้ารหัสที่ดีและใช้เพื่อเข้ารหัสข้อความให้ได้มากที่สุด แต่ในขณะเดียวกันก็มีอันตรายที่ศัตรูได้เดา (เปิด) รหัสลับและอ่านข้อมูลที่ได้รับการคุ้มครองแล้ว หากรหัสลับมีกุญแจที่เปลี่ยนได้ โดยการแทนที่กุญแจ มันเป็นไปได้ที่จะทำให้มันเป็นวิธีการที่พัฒนาโดยศัตรูไม่มีผลอีกต่อไป ในการเข้ารหัส คีย์จะเข้าใจว่าเป็นองค์ประกอบที่เปลี่ยนได้ของรหัสที่ใช้เข้ารหัสข้อความเฉพาะ ตัวอย่างเช่น ในรหัสลับ Scytala กุญแจคือเส้นผ่านศูนย์กลางของ scytala และในรหัสลับเช่นรหัสซีซาร์ กุญแจคือปริมาณการเลื่อนของตัวอักษรข้อความเข้ารหัสที่สัมพันธ์กับตัวอักษรข้อความธรรมดา ข้อพิจารณาที่อธิบายไว้นำไปสู่ความจริงที่ว่าความปลอดภัยของข้อมูลที่ได้รับการคุ้มครองเริ่มถูกกำหนดโดยคีย์เป็นหลัก รหัสตัวเองเครื่องเข้ารหัสหรือหลักการเข้ารหัสเริ่มเป็นที่รู้จักของศัตรูและพร้อมสำหรับการศึกษาเบื้องต้น แต่มีกุญแจที่ศัตรูไม่รู้จักปรากฏขึ้นซึ่งการแปลงข้อมูลที่ใช้ขึ้นอยู่กับอย่างมีนัยสำคัญ ผู้ใช้ที่ถูกต้องตามกฎหมายเหล่านี้ก่อนที่จะแลกเปลี่ยนข้อความที่เข้ารหัสลับจะต้องแลกเปลี่ยนคีย์จากศัตรูหรือตั้งค่าคีย์เดียวกันที่ปลายทั้งสองด้านของช่องทางการสื่อสาร และสำหรับปฏิปักษ์มีงานใหม่ปรากฏขึ้น - เพื่อกำหนดคีย์หลังจากนั้นจึงง่ายต่อการอ่านข้อความที่เข้ารหัสบนคีย์นี้ ให้เรากลับไปที่คำอธิบายอย่างเป็นทางการของวัตถุหลักของการเข้ารหัสลับ (รูปที่ 1 หน้า 9) ตอนนี้ต้องป้อน การเปลี่ยนแปลงครั้งสำคัญ- เพิ่มช่องทางการสื่อสารลับที่ไม่สามารถเข้าถึงศัตรูเพื่อแลกเปลี่ยนกุญแจ (ดูรูปที่ 2) การสร้างช่องทางการสื่อสารดังกล่าวค่อนข้างสมจริงเนื่องจากภาระงานโดยทั่วไปมีขนาดเล็ก โปรดทราบว่าตอนนี้ไม่มีรหัสเดียวที่เหมาะกับทุกกรณี ทางเลือกของวิธีการเข้ารหัสขึ้นอยู่กับลักษณะของข้อมูล ค่าของข้อมูล และความสามารถของเจ้าของในการปกป้องข้อมูลของตน ก่อนอื่น เราเน้นถึงความแตกต่างอย่างมากระหว่างแนวคิดหลักของการเข้ารหัส 13<- " сообщения " . „ П Рис. 2. образие видов защищаемой информации: документальная, телефон- телефонная, телевизионная, компьютерная и т. д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое зна- значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра и его параметров существенно за- зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохра- сохраняться десятилетиями, а некоторые (например, биржевые) - уже че- через несколько часов можно разгласить. Необходимо учитывать так- также и возможности того противника, от которого защищается данная информация. Одно дело - противостоять одиночке или даже бан- банде уголовников, а другое дело - мощной государственной структу- структуре. Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра. Под атакой на шифр понимают попытку вскрытия этого шифра. Понятие стойкости шифра является центральным для криптогра- криптографии. Хотя качественно понять его довольно легко, но получение стро- строгих доказуемых оценок стойкости для каждого конкретного шифра - проблема нерешенная. Это объясняется тем, что до сих пор нет необ- необходимых для решения такой проблемы математических результатов. (Мы вернемся к обсуждению этого вопроса ниже.) Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации крипто аналитике в, атаку- атакующих шифр. Такую процедуру иногда называют проверкой стойко- стойкости. Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление та- таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о целях и возможностях противника, в условиях ко- которых эти оценки получены. 14 Глава 1 Прежде всего, как это уже отмечалось выше, обычно считается, что противник знает сам шифр и имеет возможности для его предва- предварительного изучения. Противник также знает некоторые характери- характеристики открытых текстов, например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т. д. Из более специфических приведем еще три примера возможностей противника: - противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов; - противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты; - противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию. На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра. Приведем три характерных высказывания на этот счет. Английский математик Чарльз Беббидж (XIX в.): «Всякий человек, даже если он не знаком с техникой вскрытия шифров, твер- твердо считает, что сможет изобрести абсолютно стойкий шифр, и чем более умен и образован этот человек, тем более твердо это убеждение. Я сам раз- разделял эту уверенность в течение многих лет.» «Отец кибернетики» Норберт Винер: «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит за- затраченных средств, усилий и времени...» Автор шифра PGP Ф. Зиммерманн («Компьютерра», №48 от 1.12.1997, стр. 45-46): «Каждый, кто думает, что изобрел непробиваемую схему шифрования, - или невероятно редкий гений, или просто наивен и неопытен...» «Каждый программист воображает себя криптографом, что ведет к распро- распространению исключительно плохого криптообеспечения...» В заключение данного раздела сделаем еще одно замечание - о тер- терминологии. В ครั้งล่าสุด พร้อมกับคำว่า "cryptography" คำว่า "cryptology" มักพบ แต่ความสัมพันธ์ระหว่างพวกเขาไม่เข้าใจอย่างถูกต้องเสมอไป ขณะนี้ การก่อตัวของสาขาวิชาวิทยาศาสตร์ขั้นสุดท้ายกำลังเกิดขึ้น หัวข้อและงานของสาขาวิชาเหล่านี้กำลังถูกระบุ Cryptology เป็นวิทยาศาสตร์ที่ประกอบด้วยสองสาขา: การเข้ารหัสและการเข้ารหัส การเข้ารหัสเป็นศาสตร์ของวิธีการแปลงข้อมูล (เข้ารหัส) เพื่อปกป้องข้อมูลจากผู้ใช้ที่ผิดกฎหมาย การเข้ารหัสลับเป็นวิทยาศาสตร์ (และแนวปฏิบัติของการประยุกต์ใช้) เกี่ยวกับวิธีการและวิธีการทำลายตัวเลข แนวคิดพื้นฐานของการเข้ารหัส 15 ความสัมพันธ์ระหว่างการเข้ารหัสและการเข้ารหัสนั้นชัดเจน: การเข้ารหัสลับคือการป้องกัน นั่นคือ การพัฒนาของการเข้ารหัส และการเข้ารหัสคือการโจมตี กล่าวคือ การโจมตีการเข้ารหัส อย่างไรก็ตาม สาขาวิชาทั้งสองนี้มีความเกี่ยวข้องกัน และไม่มีผู้เข้ารหัสที่ดีที่ไม่เชี่ยวชาญวิธีการวิเคราะห์ด้วยความเย็น (cryptoanalysis) 3. รากฐานทางคณิตศาสตร์ ผลงานของนักคณิตศาสตร์ชาวอเมริกัน Claude Shan-Shannon ซึ่งปรากฏตัวขึ้นในช่วงกลางศตวรรษที่ 20 มีอิทธิพลอย่างมากต่อการพัฒนาวิทยาการเข้ารหัสลับ ในงานเหล่านี้ ได้มีการวางรากฐานของทฤษฎีสารสนเทศ และได้มีการพัฒนาเครื่องมือทางคณิตศาสตร์สำหรับการวิจัยในหลายๆ ด้านของวิทยาศาสตร์ที่เกี่ยวข้องกับข้อมูล นอกจากนี้ เป็นที่ยอมรับกันโดยทั่วไปว่าทฤษฎีสารสนเทศในฐานะวิทยาศาสตร์ถือกำเนิดขึ้นในปี พ.ศ. 2491 หลังจากการตีพิมพ์ผลงานของเค. แชนนอน เรื่อง “ทฤษฎีทางคณิตศาสตร์ของการสื่อสาร”1) ในงานของเขา "ทฤษฎีการสื่อสารในระบบความลับ" คลอดด์ แชนนอน ได้สรุปประสบการณ์ที่ได้รับก่อนหน้าเขาในการพัฒนาไซเฟอร์ เป็นตัวเลขที่ง่ายและได้รับความนิยมมากที่สุด ตัวอย่างทั่วไป ได้แก่ ตัวเลขซีซาร์ "อักษรดิจิทัล" ของปีเตอร์มหาราช และ A. Conan Doyle's "dancing men" "บางส่วน" ของ ciphertext ง่ายต่อการให้คำอธิบายทางคณิตศาสตร์ของตัวเลขการแทนที่ ให้ X และ Y เป็นตัวอักษรสองตัว (plaintext และ ciphertext ตามลำดับ) ที่ประกอบด้วยอักขระจำนวนเท่ากัน ให้ q: X -> Y เป็นการจับคู่แบบตัวต่อตัวของ X ถึง Y จากนั้นรหัสการแทนที่จะทำงานดังนี้: ข้อความธรรมดา x\x2 ¦¦.xn จะถูกแปลงเป็นข้อความเข้ารหัส q(x1)q( x2) ¦ ¦ -q(xn). จากชื่อแปลงการเรียงสับเปลี่ยนของตัวอักษรในข้อความธรรมดา ตัวอย่างทั่วไปของรหัสการเรียงสับเปลี่ยนคือรหัส Scytala โดยปกติ ข้อความธรรมดาจะถูกแบ่งออกเป็นส่วนที่มีความยาวเท่ากัน และแต่ละส่วนจะถูกเข้ารหัสอย่างอิสระ ตัวอย่างเช่น ความยาวของเซ็กเมนต์เท่ากับ n และ a เป็นการจับคู่แบบตัวต่อตัวของเซต (1,2,...,n) เข้าไปในตัวมันเอง จากนั้นรหัสการเรียงสับเปลี่ยนจะทำงานดังนี้: ส่วนข้อความธรรมดา x\ ... xn ถูกแปลงเป็นส่วนข้อความเข้ารหัส xx\) ... xa(n) ^ Shannon S. E. ทฤษฎีทางคณิตศาสตร์ของการสื่อสาร // Bell System Techn. J.V. 27, No. 3, 1948. P. 379-423; V. 27, No. 4, 1948. P. 623-656. 2 "ดูภาคผนวก 16 บทที่ 1 ผลลัพธ์ที่สำคัญที่สุดสำหรับการพัฒนาการเข้ารหัสคือผลลัพธ์ของ K. Shan-Shannon เกี่ยวกับการดำรงอยู่และเอกลักษณ์ของตัวเลขที่มีความปลอดภัยอย่างสมบูรณ์ ตัวเลขดังกล่าวเพียงอย่างเดียวคือสิ่งที่เรียกว่าซิงเกิ้ล - ใช้เทปซึ่งข้อความธรรมดาคือ "ด้วยคีย์สุ่มทั้งหมดที่มีความยาวเท่ากัน ผลลัพธ์นี้ได้รับการพิสูจน์โดย K. Shannon โดยใช้วิธีการทางทฤษฎีข้อมูลในการศึกษาตัวเลขที่พัฒนาโดยเขา เราจะไม่พูดถึงรายละเอียดที่นี่ เราแนะนำให้ท่านผู้อ่านที่สนใจศึกษาผลงานของ K. Shannon1" ให้เราพูดถึงคุณสมบัติของโครงสร้างของรหัสที่มีความปลอดภัยอย่างสมบูรณ์และความเป็นไปได้ในการใช้งานจริง ตัวอย่างทั่วไปและง่ายที่สุดของการนำรหัสลับที่มีความปลอดภัยอย่างสมบูรณ์มาใช้คือรหัส Vernam ซึ่งดำเนินการเพิ่มข้อความธรรมดาแบบ n-bit และคีย์ n-bit ในระดับบิต: yi = Xi®ki, i = l,...,n . ที่นี่ Xi ...xn คือข้อความธรรมดา k\,...,kn คือคีย์ y\ ¦ ¦ .yn คือข้อความเข้ารหัส เราเน้นว่าข้อกำหนดแต่ละข้อต่อไปนี้สำหรับเทปแบบใช้ครั้งเดียวมีความจำเป็นสำหรับการรักษาความปลอดภัยอย่างสมบูรณ์: 1) การสุ่มที่สมบูรณ์ (ความเท่าเทียมกัน) ของคีย์ (โดยเฉพาะอย่างยิ่ง หมายความว่าไม่สามารถสร้างคีย์โดยใช้อุปกรณ์ที่กำหนดได้) 2) ความเท่าเทียมกันของความยาวของคีย์และความยาวของข้อความธรรมดา 3) ใช้คีย์ครั้งเดียว หากมีการละเมิดเงื่อนไขอย่างน้อยหนึ่งข้อ รหัสจะหยุดปลอดภัยอย่างสมบูรณ์และความเป็นไปได้ขั้นพื้นฐานสำหรับการเปิดจะปรากฏขึ้น (แม้ว่าจะยากต่อการดำเนินการก็ตาม) แต่ปรากฎว่าเงื่อนไขเหล่านี้ทำให้รหัสที่แข็งแกร่งอย่างยิ่งมีราคาแพงและไม่สามารถใช้งานได้จริง ก่อนใช้รหัสดังกล่าว เราต้องจัดเตรียมคีย์สุ่มที่เพียงพอให้สมาชิกทุกคนและแยกความเป็นไปได้ของการนำกลับมาใช้ใหม่ และนี่เป็นเรื่องยากมากและมีราคาแพงที่จะทำ ดังที่ D. Kahn ตั้งข้อสังเกตว่า “ปัญหาในการสร้าง ลงทะเบียน แจกจ่าย และยกเลิกคีย์อาจดูไม่ซับซ้อนเกินไปสำหรับคนที่ไม่มีประสบการณ์ในการส่งข้อความผ่านช่องทางการสื่อสารทางทหาร แต่ในช่วงสงครามปริมาณข้อความที่ส่งยังสร้างความสับสนแม้แต่นักส่งสัญญาณมืออาชีพ . สามารถเข้ารหัสคำได้หลายแสนคำต่อวัน การสร้างสัญญาณสำคัญนับล้านจะต้องใช้เงินจำนวนมากและจะเกี่ยวข้องกับการลงทุนขนาดใหญ่ เนื่องจากแต่ละข้อความต้องมีคีย์ของตัวเอง ไม่ซ้ำใคร และเลียนแบบไม่ได้ 1 "ดูภาคผนวก แนวคิดพื้นฐานของการเข้ารหัส 17 การใช้ระบบในอุดมคติจะต้องมีการส่งอักขระอย่างน้อยเท่ากับจำนวนข้อมูลทางทหารทั้งหมด ถ่ายทอด” ด้วยเหตุผลเหล่านี้ รหัสลับที่รัดกุมอย่างยิ่งจึงถูกใช้ในเครือข่ายการสื่อสารที่มีข้อมูลที่ส่งเพียงเล็กน้อยเท่านั้นซึ่งโดยปกติแล้วจะเป็นเครือข่ายสำหรับการส่งข้อมูลของรัฐบาลที่สำคัญโดยเฉพาะ เลขศูนย์ที่รัดกุม อย่างน้อยก็ในทางทฤษฎีก็สามารถแตกได้ คำถามเดียวคือ ว่าฝ่ายตรงข้ามมีความแข็งแกร่ง วิธีการ และเวลาเพียงพอในการพัฒนาและใช้งานอัลกอริทึมที่สอดคล้องกันหรือไม่ โดยปกติ แนวคิดนี้จะแสดงดังนี้: ปฏิปักษ์ที่มีทรัพยากรไม่จำกัดสามารถทำลายรหัสลับที่ไม่แน่นหนาใดๆ ได้ แล้วผู้ใช้ที่ถูกต้องควรทำอย่างไรในสถานการณ์นี้ การเลือกรหัสสำหรับตัวเองจะเป็นการดีที่สุดที่จะพิสูจน์ว่าไม่มีปฏิปักษ์ใดสามารถเป็นเวลาหลายปีและได้รับการประเมินทางทฤษฎีของการต่อต้าน แต่น่าเสียดายที่ทฤษฎีทางคณิตศาสตร์ยังไม่ได้ให้ทฤษฎีบทที่จำเป็น - พวกเขาอ้างถึงปัญหาที่ยังไม่ได้แก้ไขของขอบเขตล่างสำหรับความซับซ้อนในการคำนวณของปัญหา \ ดังนั้น ผู้ใช้จึงเหลือหนทางเดียว - เพื่อรับการประเมินเชิงปฏิบัติของการต่อต้าน เส้นทางนี้ประกอบด้วยขั้นตอนต่อไปนี้: "- เข้าใจและชัดเจนว่าเราจะปกป้องข้อมูลของปฏิปักษ์ประเภทใด; จำเป็นต้องเข้าใจว่าฝ่ายตรงข้ามรู้หรือสามารถเรียนรู้เกี่ยวกับระบบตัวเลขได้อย่างชัดเจนรวมถึงกองกำลังใดและ หมายความว่าเขาจะสามารถใช้มันเพื่อเปิดมันได้ - วางตัวเองให้อยู่ในตำแหน่งของศัตรูและพยายามโจมตีตัวเลขจากตำแหน่งของเขาเช่นพัฒนาอัลกอริธึมต่าง ๆ เพื่อทำลายรหัส ในขณะที่จำเป็นต้องจัดหาแบบจำลองให้กับ ขอบเขตสูงสุด - การสร้างแบบจำลองกองกำลัง เครื่องมือ และความสามารถของศัตรู - อัลกอริธึมที่ดีที่สุดที่พัฒนาขึ้นสามารถใช้สำหรับการประเมินความปลอดภัยของรหัสในเชิงปฏิบัติ ในภาพประกอบ จะมีประโยชน์ที่จะกล่าวถึงสองวิธีที่ง่ายที่สุดในการทำลาย รหัส: การเดาคีย์แบบสุ่ม (ใช้งานได้ด้วยความน่าจะเป็นเล็กน้อย แต่มีความซับซ้อนเล็กน้อย) และการแจงนับของคีย์ทั้งหมดในแถวจนพบความจริง (ใช้งานได้เสมอ แต่มีความซับซ้อนสูงมาก) เรายังทราบด้วยว่าการโจมตีคีย์ไม่จำเป็นเสมอไป: สำหรับรหัสลับบางตัว เป็นไปได้ในทันที แม้จะไม่รู้คีย์เพื่อกู้คืนข้อความธรรมดาจากข้อความเข้ารหัส 18 บทที่ 1 4. ทิศทางใหม่ ในปี 1983 ในหนังสือ "รหัสและคณิตศาสตร์" โดย M. N. Arshinov และ L. E. Sa-Sadovsky (ห้องสมุด "Kvant") มันถูกเขียนว่า: "มีหลายวิธีในการเข้ารหัสและส่วนใหญ่ มีแนวโน้มว่านี่คือพื้นที่ที่ไม่จำเป็นต้องประดิษฐ์สิ่งใหม่โดยพื้นฐานอีกต่อไป อย่างไรก็ตาม นี่เป็นความเข้าใจผิดครั้งใหญ่อีกประการหนึ่งเกี่ยวกับการเข้ารหัส ย้อนกลับไปในปี 1976 ผลงานของนักคณิตศาสตร์ชาวอเมริกันรุ่นเยาว์ W. Diffie และ M. E. Hellman "New Trends in Cryptography"1" ได้รับการตีพิมพ์ ซึ่งไม่เพียงแต่เปลี่ยนการเข้ารหัสอย่างมีนัยสำคัญ แต่ยังนำไปสู่การเกิดขึ้นและการพัฒนาอย่างรวดเร็วของแนวโน้มใหม่ทางคณิตศาสตร์ แนวคิดหลัก "new cryptography" เป็นแนวคิดของฟังก์ชันทางเดียว (ดูข้อมูลเพิ่มเติมในบทที่ 2) ฟังก์ชันทางเดียวเรียกว่าฟังก์ชัน F: X -> Y ซึ่งมีคุณสมบัติสองประการ: a) มีอัลกอริธึมพหุนามสำหรับคำนวณค่าของ F (x), b) ไม่มีอัลกอริธึมพหุนามสำหรับการกลับฟังก์ชัน F (เช่น การแก้สมการ F(x) = y เทียบกับ x ดูหน้า 30 สำหรับคำจำกัดความที่แน่นอน) สำหรับข้อจำกัดความซับซ้อนของการคำนวณและการผกผัน คำถามของการมีอยู่ของฟังก์ชันทางเดียวยังคงเปิดอยู่ แนวคิดใหม่อีกประการหนึ่งคือแนวคิดของฟังก์ชันที่มีความลับ บางครั้งก็ใช้ ฟังก์ชันเทอมพร้อมกับดัก ฟังก์ชันที่มี K ลับคือฟังก์ชัน Fk: X -> Y ที่ขึ้นอยู่กับพารามิเตอร์ K และมีคุณสมบัติสามประการ: a) มีอัลกอริธึมพหุนามสำหรับคำนวณค่าของ Fk(x) สำหรับ K และ x ใดๆ; b) ไม่มีอัลกอริธึมพหุนามสำหรับการกลับค่า Fa สำหรับ K ที่ไม่รู้จัก c) มีอัลกอริธึมพหุนามสำหรับการกลับค่า Fk ด้วย K ที่รู้จัก สามารถพูดได้เช่นเดียวกันเกี่ยวกับการมีอยู่ของฟังก์ชันที่มีความลับเหมือนกับที่พูดถึงฟังก์ชันทางเดียว เพื่อวัตถุประสงค์ในทางปฏิบัติของการเข้ารหัส มีการสร้างฟังก์ชันหลายอย่างที่อาจกลายเป็นฟังก์ชันที่มีความลับ สำหรับพวกเขา คุณสมบัติ b) ยังไม่ได้รับการพิสูจน์อย่างจริงจัง แต่เชื่อกันว่าปัญหาการผกผันเทียบเท่ากับปัญหาทางคณิตศาสตร์ที่ยากบางอย่างที่ได้รับการศึกษามาเป็นเวลานาน ฟังก์ชันที่เป็นที่รู้จักและได้รับความนิยมมากที่สุดคือฟังก์ชันทฤษฎีจำนวนที่สร้างรหัส RSA (ดูเพิ่มเติมในบทที่ 4 สำหรับข้อมูลเพิ่มเติม) "" Diffie W. , Hellman M. E. ความปลอดภัยและการต่อต้านการเลียนแบบ ความรู้เบื้องต้นเกี่ยวกับการเข้ารหัส // TIEER V. 67, No. 3, 1979. แนวคิดพื้นฐานของการเข้ารหัส 19 การใช้ฟังก์ชั่นที่มีความลับในการเข้ารหัสช่วยให้: 1) จัดระเบียบการแลกเปลี่ยนข้อความที่เข้ารหัสโดยใช้ช่องทางการสื่อสารแบบเปิดเท่านั้นเช่นปฏิเสธช่องทางการสื่อสารลับในเบื้องต้น การแลกเปลี่ยนกุญแจ 2) รวมปัญหาทางคณิตศาสตร์ที่ยากในปัญหาการถอดรหัสตัวเลขและเพิ่มความถูกต้องของการรักษาความปลอดภัยของตัวเลข 3) แก้ปัญหาการเข้ารหัสใหม่นอกเหนือจากการเข้ารหัส (ลายเซ็นดิจิทัลอิเล็กทรอนิกส์ ฯลฯ ) ให้เราอธิบาย เช่น วิธีการใช้งานข้อ 1) ผู้ใช้ A ที่ต้องการรับข้อความที่เข้ารหัสจะต้องเลือกฟังก์ชั่น Fk ที่มีความลับ K เขาแจ้งให้ผู้มีส่วนได้ส่วนเสียทั้งหมดทราบ (เช่น เผยแพร่) รายละเอียดของฟังก์ชัน Fk เป็นอัลกอริธึมการเข้ารหัสของเขา แต่ในขณะเดียวกันเขาก็ไม่บอกความหมายของความลับของเคให้ใครรู้และเก็บเป็นความลับ ตอนนี้ถ้าผู้ใช้ B ต้องการส่งข้อมูลที่ได้รับการป้องกันไปยังผู้ใช้ A? X จากนั้นจะคำนวณ y = Fk(x) และส่ง y ไปยังช่องสัญญาณที่เปิดอยู่ให้กับผู้ใช้ A เนื่องจาก A รู้วิธีกลับค่า Fk สำหรับ K ลับของเขา เขาจึงคำนวณ x จากค่า y ที่ได้รับ ไม่มีใครรู้จัก K ดังนั้น เนื่องจากคุณสมบัติ b) ของฟังก์ชันที่มีความลับ จึงไม่สามารถคำนวณข้อมูลที่ได้รับการป้องกัน x ในเวลาพหุนามจากข้อความเข้ารหัสที่รู้จัก Fk(x) ระบบที่อธิบายนี้เรียกว่าระบบเข้ารหัสคีย์สาธารณะ เนื่องจากอัลกอริธึมการเข้ารหัส Fk เป็นแบบสาธารณะหรือแบบเปิด เมื่อเร็ว ๆ นี้ cryptosystems ดังกล่าวเรียกว่าไม่สมมาตรเนื่องจากมีความไม่สมมาตรในอัลกอริทึม: อัลกอริธึมการเข้ารหัสและถอดรหัสต่างกัน ในทางตรงกันข้ามกับระบบดังกล่าว การเข้ารหัสแบบดั้งเดิมเรียกว่าสมมาตร: ในนั้น กุญแจสำหรับการเข้ารหัสและถอดรหัสเหมือนกัน สำหรับระบบอสมมาตร อัลกอริธึมการเข้ารหัสเป็นที่รู้จักกันดี แต่เป็นไปไม่ได้ที่จะสร้างอัลกอริธึมถอดรหัสขึ้นมาใหม่ในเวลาพหุนาม Diffie และ Hellman แนะนำให้ใช้แนวคิดที่อธิบายข้างต้นสำหรับอิเล็กทรอนิกส์ด้วย ลายเซ็นดิจิทัล ข้อความที่ไม่สามารถปลอมแปลงได้ในเวลาพหุนาม ให้ผู้ใช้ A ไม่ต้องเซ็นข้อความ x เมื่อรู้ความลับ K เขาพบว่า y นั้น Pk(y) - x และพร้อมกับข้อความ x ส่ง y ไปยังผู้ใช้ B เป็นลายเซ็นดิจิทัลของเขา ผู้ใช้ B เก็บ y ไว้เป็นหลักฐานว่า A เซ็นข้อความ x ข้อความที่เซ็นชื่อด้วยลายเซ็นดิจิทัลถือเป็นคู่ (x, y) โดยที่ x คือข้อความ y คือคำตอบของสมการ Pk(y) - x, Fk"¦ X -> Y คือฟังก์ชัน ด้วยความลับที่รู้กันดีว่าทุกคนมีปฏิสัมพันธ์ จากคำจำกัดความของฟังก์ชัน Fk คุณสมบัติที่เป็นประโยชน์ของลายเซ็นดิจิทัลต่อไปนี้ชัดเจน: 2) สมาชิกที่รู้กุญแจสาธารณะ กล่าวคือ ฟังก์ชัน Fk\ เองสามารถตรวจสอบความถูกต้องของลายเซ็นได้ 3 ) ในกรณีที่มีข้อพิพาทเป็นไปไม่ได้ที่จะปฏิเสธลายเซ็นเนื่องจากไม่สามารถปลอมแปลงได้ 4) ข้อความที่ลงนาม (x, y) สามารถทำได้โดยไม่ต้องกลัวความเสียหาย ส่งต่อผ่านช่องทางการสื่อสารใด ๆ นอกเหนือจากหลักการสร้างระบบเข้ารหัสด้วย a กุญแจสาธารณะ Diffie และ Hellman ในงานเดียวกันได้เสนอแนวคิดใหม่อีกประการหนึ่ง - การกระจายกุญแจสาธารณะ พวกเขาถามตัวเองด้วยคำถาม: เป็นไปได้ไหมที่จะจัดระเบียบขั้นตอนดังกล่าวสำหรับการโต้ตอบของสมาชิก A และ B ผ่านช่องทางการสื่อสารแบบเปิดเพื่อแก้ไขงานต่อไปนี้: 1) ในตอนแรก A และ B ไม่มีข้อมูลลับทั่วไป แต่ในตอนท้ายของขั้นตอนข้อมูลลับที่ใช้ร่วมกันดังกล่าว (คีย์ทั่วไป) จะปรากฏขึ้นสำหรับ A และ B นั่นคือมันถูกสร้างขึ้น; 2) ศัตรูที่อยู่เฉยๆ ที่สกัดกั้นการส่งข้อมูลทั้งหมดและรู้ว่า A และ B ต้องการรับ อย่างไรก็ตาม ไม่สามารถกู้คืนคีย์ทั่วไป A และ B ที่สร้างขึ้นได้ Diffie และ Hellman เสนอให้แก้ปัญหาเหล่านี้โดยใช้ฟังก์ชันฟังก์ชัน F(x ) = ax (mod p) โดยที่ p เป็นจำนวนเฉพาะจำนวนมาก x คือจำนวนธรรมชาติโดยอำเภอใจ q คือองค์ประกอบดั้งเดิมของสนาม GF(p) เป็นที่ยอมรับกันโดยทั่วไปว่าการผกผันของฟังก์ชันขวาน (modp) เช่น ล็อกลอการิทึมแบบไม่ต่อเนื่องเป็นปัญหาทางคณิตศาสตร์ที่ยาก (ดูรายละเอียดเพิ่มเติมในบทที่ 4) โพรซีเดอร์เอง หรืออย่างที่พวกเขาพูด โปรโตคอลสำหรับการสร้างคีย์ที่ใช้ร่วมกัน มีการอธิบายดังนี้ สมาชิก A และ B สุ่มเลือกหมายเลขธรรมชาติอย่างละตัว - พูดว่า xa และ xb พวกเขาเก็บองค์ประกอบเหล่านี้เป็นความลับ นอกจากนี้ แต่ละองค์ประกอบยังคำนวณองค์ประกอบใหม่: y A = otXA (mod p), y b = aXb (mod p) (ตัวเลข p และ a ถือเป็นสาธารณะ ) จากนั้นพวกเขาแลกเปลี่ยนองค์ประกอบเหล่านี้ผ่านช่องทางการสื่อสาร ตอนนี้สมาชิก A เมื่อได้รับ uv และรู้องค์ประกอบลับ xa แล้ว คำนวณองค์ประกอบใหม่: uxvA (modp) = (aXB)XA (modp) สมาชิก B ทำหน้าที่คล้ายกัน: uxAv (mod p) = (aXA)Xv (mod p) แนวคิดพื้นฐานของการเข้ารหัส 21 ดังนั้น A และ B มีองค์ประกอบฟิลด์ทั่วไปเท่ากับ aXlXv องค์ประกอบนี้ประกาศโดยคีย์ทั่วไปของ A และ B จากคำอธิบายของโปรโตคอล เป็นที่ชัดเจนว่าฝ่ายตรงข้ามรู้ p, a, aXA, aXb ไม่รู้จัก xa และ xts และต้องการทราบ aXXb ในปัจจุบัน ไม่มีอัลกอริธึมที่เป็นปฏิปักษ์ใดมีประสิทธิภาพมากกว่าลอการิทึมแบบแยกส่วน และนี่เป็นปัญหาทางคณิตศาสตร์ที่ยาก ความก้าวหน้าในการพัฒนารูปแบบลายเซ็นดิจิทัลและการกระจายคีย์สาธารณะทำให้สามารถนำแนวคิดเหล่านี้ไปใช้กับปัญหาอื่น ๆ ของการโต้ตอบระหว่างสมาชิกระยะไกลได้เช่นกัน ดังนั้นทิศทางใหม่ที่ยอดเยี่ยมของการเข้ารหัสเชิงทฤษฎีจึงเกิดขึ้น - โปรโตคอลการเข้ารหัสลับการเข้ารหัส (ดูบทที่ 3 สำหรับรายละเอียดเพิ่มเติม) วัตถุประสงค์ของการศึกษาทฤษฎีของโปรโตคอลการเข้ารหัสลับคือสมาชิกระยะไกลโต้ตอบตามกฎผ่านช่องทางการสื่อสารแบบเปิด จุดประสงค์ของการโต้ตอบของสมาชิกคือการแก้ปัญหาบางอย่าง ยังมีปฏิปักษ์ที่ไล่ตามเป้าหมายของตัวเอง ในกรณีนี้ ศัตรูในภารกิจต่าง ๆ อาจมีความสามารถต่างกัน เช่น เขาสามารถโต้ตอบกับ สมาชิก-subscribers ในนามของสมาชิกรายอื่นหรือแทรกแซงการแลกเปลี่ยนข้อมูลระหว่างสมาชิก ฯลฯ ศัตรูอาจเป็นหนึ่งในสมาชิกหรือสมาชิกหลายคนที่สมรู้ร่วมคิด ต่อไปนี้คือตัวอย่างเพิ่มเติมของงานที่สมาชิกระยะไกลแก้ไขได้ (เราแนะนำให้ผู้อ่านคิดตัวอย่างเพิ่มเติมตามรสนิยมของเขา) 1. สมาชิกสองคนที่ไม่ไว้วางใจซึ่งกันและกันโต้ตอบ พวกเขาต้องการเซ็นสัญญา สิ่งนี้จะต้องทำในลักษณะที่ป้องกันสถานการณ์ต่อไปนี้: หนึ่งในสมาชิกได้รับลายเซ็นของอีกฝ่าย แต่ตัวเขาเองไม่ได้ลงนาม โปรโตคอลสำหรับการแก้ปัญหานี้มักจะเรียกว่าโปรโตคอลการลงนามในสัญญา 2. สมาชิกสองคนที่ไม่ไว้วางใจซึ่งกันและกันโต้ตอบ พวกเขาต้องการจับสลากด้วยเหรียญ ควรทำในลักษณะที่ผู้ใช้ที่พลิกเหรียญไม่สามารถเปลี่ยนผลการโยนหลังจากได้รับเดาจากผู้ใช้เดาผลนี้ โปรโตคอลในการแก้ปัญหานี้เรียกว่าโปรโตคอลการโยนเหรียญ ให้เราอธิบายหนึ่งในโปรโตคอลที่ง่ายที่สุดสำหรับการโยนเหรียญทางโทรศัพท์ (ที่เรียกว่าโครงการ Blume-Micali) ในการใช้งาน สมาชิก A และ B ต้องมีฟังก์ชันทางเดียว /: X -> Y ที่ตรงตามเงื่อนไขต่อไปนี้: 1) X คือชุดของจำนวนเต็มที่มีจำนวนคู่และเลขคี่เหมือนกัน 22 บทที่ 1 2) ตัวเลขใด ๆ xi,X2 ? X มีหนึ่งภาพ )(x\) - หนึ่งพาริตี; 3) จากรูปแบบ f(x) จะเป็น "ยาก" ในการคำนวณความเท่าเทียมกันของอาร์กิวเมนต์ที่ไม่รู้จัก x บทบาทของการโยนเหรียญเล่นโดยการเลือกองค์ประกอบ x 6 X ที่สุ่มและมีโอกาสเท่ากัน และบทบาทของหัวและก้อยจะเล่นโดยความเท่าเทียมและความแปลกประหลาดของ x ตามลำดับ ให้ A เป็นผู้โยนเหรียญ และ B เป็นผู้เดา โปรโตคอลประกอบด้วยขั้นตอนต่อไปนี้: 1) A เลือก x (“โยนเหรียญ”), เข้ารหัส x, เช่น คำนวณ y = f(x) และส่ง y ไปยังสมาชิก B; 2) B รับ y พยายามเดาความเท่าเทียมกันของ x และส่งการเดาไปยังสมาชิก A 3) A ได้รับการเดาจาก B และบอก B ถ้าเขาเดาถูกต้องโดยส่งหมายเลขที่เลือก x ไปให้เขา 4) B ตรวจสอบดูว่า A กำลังโกงหรือไม่โดยคำนวณค่าของ f(x) และเปรียบเทียบกับค่าของ y ที่ได้รับในขั้นตอนที่สอง 3. สมาชิกสองคน A และ B โต้ตอบกัน (ตัวอย่างทั่วไป: A เป็นลูกค้าธนาคาร B คือธนาคาร) สมาชิก A ต้องการพิสูจน์ให้สมาชิก B เห็นว่าเขาเป็น A ไม่ใช่คู่ต่อสู้ โปรโตคอลสำหรับการแก้ปัญหานี้มักจะเรียกว่าโปรโตคอลการระบุสมาชิก 4. สมาชิกระยะไกลหลายคนที่ได้รับคำสั่งซื้อจากศูนย์เดียวโต้ตอบ สมาชิกบางคนรวมทั้งศูนย์อาจเป็นฝ่ายตรงข้าม จำเป็นต้องพัฒนากลยุทธ์การดำเนินการแบบครบวงจรที่เป็นประโยชน์ต่อสมาชิก ปัญหานี้มักจะเรียกว่าปัญหาของนายพลไบแซนไทน์และโปรโตคอลของการแก้ปัญหาเรียกว่าโปรโตคอลของข้อตกลงไบแซนไทน์ ให้เราอธิบายตัวอย่างที่ปัญหานี้เป็นหนี้ชื่อของมัน ไบแซนเทียม - ไบแซนเทียม คืนก่อนศึกใหญ่. กองทัพไบแซนไทน์ประกอบด้วยพยุหเสนา n พยุหเสนา ซึ่งแต่ละกองอยู่ภายใต้นายพลของตนเอง นอกจากนี้ กองทัพบกยังมีผู้บัญชาการทหารสูงสุดที่กำกับนายพล อย่างไรก็ตาม จักรวรรดิกำลังตกต่ำ และถึงหนึ่งในสามของนายพล รวมทั้งผู้บัญชาการทหารสูงสุด อาจเป็นคนทรยศ ในตอนกลางคืนนายพลแต่ละคนได้รับคำสั่งจากผู้บัญชาการทหารสูงสุดเกี่ยวกับการดำเนินการในช่วงเช้าและสอง วา-ตัวแปร คำสั่ง: "โจมตี" หรือ "ถอย" ถ้านายพลที่ซื่อสัตย์ทุกคนโจมตี พวกเขาก็ชนะ หากพวกเขาทั้งหมดล่าถอย พวกเขาก็สามารถช่วยกองทัพได้ แต่ถ้าบางคนโจมตีและถอยกลับ พวกเขาก็พ่ายแพ้ หากผู้บัญชาการทหารสูงสุดกลายเป็นคนทรยศ เขาก็สามารถออกคำสั่งต่างๆ ให้กับแม่ทัพที่แตกต่างกันได้ ดังนั้นคำสั่งของผู้บัญชาการทหารสูงสุดจึงไม่ควรปฏิบัติตามโดยปริยาย หากนายพลแต่ละคนทำหน้าที่โดยอิสระจากผู้อื่น ผลลัพธ์ก็อาจเป็นหายนะได้ เห็นได้ชัดว่านายพลจำเป็นต้องแลกเปลี่ยนข้อมูลกัน (เกี่ยวกับคำสั่งที่ได้รับ) เพื่อที่จะตกลงกันได้ แนวคิดพื้นฐานของการเข้ารหัส 23 ความเข้าใจในโปรโตคอลและวิธีการต่างๆ ในการก่อสร้างส่งผลให้ สู่การเกิดขึ้นของแบบจำลองทางคณิตศาสตร์ที่มีผลสองแบบ - ระบบการพิสูจน์เชิงโต้ตอบและการพิสูจน์ที่ไม่มีความรู้ การศึกษาทางคณิตศาสตร์ของวัตถุใหม่เหล่านี้ได้พิสูจน์ข้อความจำนวนมากที่มีประโยชน์มากในการพัฒนาโปรโตคอลการเข้ารหัส (ดูบทที่ 2 สำหรับข้อมูลเพิ่มเติมเกี่ยวกับเรื่องนี้) ระบบการพิสูจน์เชิงโต้ตอบ (P, V, S) เป็นที่เข้าใจกันว่าเป็นโปรโตคอลสำหรับการโต้ตอบของสมาชิกสองคน: P (พิสูจน์) และ V (พิสูจน์) สมาชิก P ต้องการพิสูจน์ต่อ V ว่าคำสั่ง 5 เป็นจริง ที่ ในเวลาเดียวกันสมาชิก V อย่างอิสระโดยไม่ได้รับความช่วยเหลือจาก P ไม่สามารถตรวจสอบคำสั่ง S ได้ (ดังนั้น V จึงเรียกว่าผู้ตรวจสอบ ผู้สมัครสมาชิก P ยังสามารถเป็นปฏิปักษ์ที่ต้องการพิสูจน์ให้ V เห็นว่าคำสั่ง S เป็นจริงแม้ว่า เป็นเท็จ โปรโตคอลสามารถประกอบด้วยการแลกเปลี่ยนข้อความหลายรอบระหว่าง P และ V และต้องเป็นไปตามเงื่อนไขสองประการ: 1) ความสมบูรณ์ - ถ้า 5 เป็นจริง สมาชิก P จะโน้มน้าวให้สมาชิก V ยอมรับ; 2) ความถูกต้อง - ถ้า 5 เป็นเท็จ ดังนั้นสมาชิก P ไม่น่าจะโน้มน้าวผู้สมัครสมาชิก V ว่า 5 เป็นจริง เพื่อความง่าย เราได้แทนที่สูตรทางคณิตศาสตร์ที่แน่นอนด้วยคำว่า "ไม่น่าจะ" เราเน้นว่าในคำจำกัดความของระบบ (P, V, S) ไม่อนุญาตให้ V อาจเป็นปฏิปักษ์ แต่ถ้าวีกลายเป็นปฏิปักษ์ที่ต้องการ "ค้นหา" ข้อมูลที่เป็นประโยชน์ใหม่เกี่ยวกับข้อความที่ 5 จาก P ล่ะ? ในกรณีนี้ แน่นอนว่า P อาจไม่ต้องการให้สิ่งนี้เกิดขึ้นจากการทำงานของโปรโตคอล (P, V, S) โปรโตคอล (P, V, S) ที่แก้ปัญหาดังกล่าวเรียกว่าการพิสูจน์ความรู้เป็นศูนย์และต้องปฏิบัติตามนอกเหนือจากเงื่อนไข 1) และ 2) เงื่อนไขต่อไปนี้: 3) ศูนย์ความรู้ - อันเป็นผลมาจากการดำเนินการ ของโปรโตคอล (P, V, S) สมาชิก V จะไม่เพิ่มความรู้ของเขาเกี่ยวกับคำสั่ง S หรือกล่าวอีกนัยหนึ่งก็คือจะไม่สามารถดึงข้อมูลใด ๆ เกี่ยวกับสาเหตุที่ S เป็นจริงได้ 5. บทสรุป ในช่วงไม่กี่ปีที่ผ่านมา การเข้ารหัสและวิธีการเข้ารหัสได้กลายเป็นส่วนหนึ่งในชีวิตของเราและแม้กระทั่งชีวิตประจำวันมากขึ้น นี่คือตัวอย่างบางส่วน. เมื่อส่งอีเมล ในบางกรณีเราจะตอบคำถามในเมนูว่า "ฉันต้องใช้โหมดการเข้ารหัสหรือไม่" เจ้าของบัตรธนาคาร-ธนาคารอัจฉริยะ ซึ่งระบุที่อยู่ธนาคารผ่านเครื่องชำระเงิน ขั้นแรกจะดำเนินโปรโตคอลการตรวจสอบความถูกต้องของบัตรเข้ารหัส ผู้ใช้อินเทอร์เน็ตอาจคุ้นเคยกับการอภิปรายเกี่ยวกับการนำมาตรฐานลายเซ็นดิจิทัลไปใช้ที่เป็นไปได้สำหรับหน้าเว็บเหล่านั้นที่มีข้อมูล "สำคัญ" (กฎหมาย รายการราคา ฯลฯ) เมื่อเร็ว ๆ นี้ ผู้ใช้เครือข่ายได้เริ่มระบุหลังนามสกุลพร้อมกับ "อีเมล ... " ที่คุ้นเคยแล้วและ "ลายนิ้วมือคีย์สาธารณะ ... " ที่คุ้นเคยน้อยกว่า มีตัวอย่างมากขึ้นทุกวัน เป็นแอปพลิเคชั่นใหม่ของการเข้ารหัสซึ่งเป็นหนึ่งในแหล่งที่มาของการพัฒนา บทที่ 2 ทฤษฎีการเข้ารหัสและความซับซ้อน จุดเน้นของบทนี้คือการชี้แจงแนวคิดที่สำคัญที่เกี่ยวข้องกับการใช้วิธีการเชิงทฤษฎีที่ซับซ้อนในการเข้ารหัส อธิบายโดยความจำเป็นเป็นทางการไม่เพียงพอ - คำจำกัดความหลายหน้าเป็นเรื่องปกติสำหรับการเข้ารหัสทางคณิตศาสตร์ สันนิษฐานว่าผู้อ่านคุ้นเคยกับพื้นฐานของทฤษฎีความซับซ้อนในการคำนวณ: แนวคิดของเครื่องทัวริง คลาส P และ NP (ดู ) เช่นเดียวกับบทที่ 1 ของหนังสือเล่มนี้ 1. บทนำ ในการเข้ารหัสเชิงทฤษฎี มีสองวิธีหลักในการกำหนดความปลอดภัยของระบบเข้ารหัสและโปรโตคอลการเข้ารหัส (ในสิ่งต่อไปนี้ เราจะใช้รูปแบบการเข้ารหัสคำทั่วไปด้วย): ข้อมูล-ทฤษฎี และความซับซ้อน-ทฤษฎี แนวทางข้อมูล-ทฤษฎีถือว่าฝ่ายตรงข้ามโจมตีรูปแบบการเข้ารหัสไม่มีแม้แต่โอกาสทางทฤษฎีที่จะได้รับข้อมูลที่เพียงพอเพื่อให้บรรลุเป้าหมายของเขา ตัวอย่างคลาสสิกที่นี่คือรหัส Vernam ที่มีปุ่มแบบใช้ครั้งเดียว ซึ่งทนทานต่อศัตรูแบบพาสซีฟอย่างแน่นอน แผนงานการเข้ารหัสลับส่วนใหญ่ที่ใช้ในทางปฏิบัติไม่มีความปลอดภัยสูงเช่นนี้ ยิ่งไปกว่านั้น โดยปกติแล้ว การระบุอัลกอริธึมที่ทำงานโดยต้องเผชิญหน้ากับคู่ต่อสู้มักเป็นเรื่องง่าย แต่โดยทั่วไปแล้วไม่ใช่ในทางปฏิบัติ พิจารณาตัวอย่างต่อไปนี้ ตัวอย่างที่ 1 (ระบบเข้ารหัสคีย์สาธารณะ) Cryptosystem - ระบบเข้ารหัสคีย์สาธารณะถูกกำหนดโดยสมบูรณ์โดยสามอัลกอริธึม - อัลกอริธึม: การสร้างคีย์ การเข้ารหัส และการถอดรหัส อัลกอริทึมการสร้างคีย์ G นั้นเปิดเผยต่อสาธารณะ ทุกคนสามารถให้สตริงสุ่ม r ที่มีความยาวที่เหมาะสมเป็นอินพุตและรับกุญแจ (A "1, Xr) คีย์สาธารณะ K \ ถูกเผยแพร่และเป็นความลับ คีย์ K-iและสตริงสุ่ม z จะถูกเก็บเป็นความลับ อัลกอริธึมการเข้ารหัส Ekx และการถอดรหัส D^2 เป็นเช่นนั้นหาก (K\, K-i) เป็นคู่คีย์ที่สร้างโดยอัลกอริทึม G ดังนั้น Dk2(Ek1 [m)) = m สำหรับข้อความธรรมดา m เพื่อความง่าย เราคิดว่า ข้อความธรรมดาและรหัสลับมีความยาวเท่ากัน n นอกจากนี้ เราคิดว่าข้อความธรรมดา การเข้ารหัสลับ และคีย์ทั้งสองเป็นสตริงในอักษรไบนารี สมมุติว่าฝ่ายตรงข้ามโจมตีระบบเข้ารหัสนี้ เขารู้กุญแจสาธารณะ K\ แต่ไม่รู้รหัสที่เกี่ยวข้อง ความลับ คีย์ กี้. ฝ่ายตรงข้ามได้สกัดกั้นการเข้ารหัสลับ d และพยายามค้นหาข้อความ m โดยที่ d = Ec^(m) เนื่องจากอัลกอริธึมการเข้ารหัสเป็นที่รู้จักกันดี ฝ่ายตรงข้ามสามารถทำซ้ำผ่านข้อความที่เป็นไปได้ทั้งหมดที่มีความยาว n คำนวณสำหรับแต่ละข้อความดังกล่าว TP( cryptogram di = Ekx (mn-r) และเปรียบเทียบ di กับ d กับข้อความที่ di = d และจะเป็นข้อความธรรมดาที่ต้องการ ถ้าคุณโชคดี จะหาข้อความธรรมดาได้เร็วพอ ในกรณีที่เลวร้ายที่สุด การแจงนับจะเสร็จสิ้นภายในเวลา 2"T(n) โดยที่ T( n) คือเวลาที่ต้องใช้ในการคำนวณฟังก์ชัน Ek จากข้อความที่มีความยาว n หากข้อความมีความยาว 1,000 บิต การแจงนับดังกล่าวไม่สามารถทำได้ในทางปฏิบัติบนคอมพิวเตอร์ที่มีประสิทธิภาพสูงสุดใดๆ เราได้พิจารณาแล้ว วิธีเดียวที่เป็นไปได้ในการโจมตีระบบเข้ารหัสลับและอัลกอริธึมการค้นหาข้อความธรรมดาที่ง่ายที่สุด มักเรียกว่าอัลกอริธึมข้อความแบบเต็ม นอกจากนี้ยังใช้อีกชื่อหนึ่งว่า "วิธีกำลังดุร้าย" อีกอัลกอริธึมง่ายๆ สำหรับการค้นหาข้อความธรรมดาคือการคาดเดา อัลกอริธึมที่ชัดเจนนี้ต้องการเพียงเล็กน้อย คำนวณแต่ได้ผล ด้วยความน่าจะเป็นเล็กน้อย (สำหรับข้อความที่มีความยาวมาก) ในความเป็นจริง ฝ่ายตรงข้ามอาจพยายามโจมตีระบบการเข้ารหัสลับในรูปแบบต่างๆ และใช้อัลกอริธึมการค้นหาข้อความธรรมดาที่หลากหลายและซับซ้อนยิ่งขึ้น เป็นเรื่องปกติที่จะต้องพิจารณาว่าระบบเข้ารหัสลับมีความปลอดภัย หากอัลกอริธึมดังกล่าวต้องใช้การคำนวณในปริมาณที่แทบจะเป็นไปไม่ได้ หรือทำงานได้ด้วยความน่าจะเป็นเพียงเล็กน้อย (ในกรณีนี้ ปฏิปักษ์ไม่เพียงแต่ใช้อัลกอริธึมที่กำหนดขึ้นเองเท่านั้น แต่ยังใช้อัลกอริธึมความน่าจะเป็นได้ด้วย) นี่คือแนวทางความซับซ้อน-ทฤษฎีในการกำหนดความปลอดภัย ในการนำไปใช้โดยสัมพันธ์กับรูปแบบการเข้ารหัสประเภทใดประเภทหนึ่ง จำเป็นต้องดำเนินการดังต่อไปนี้: 1) ให้คำจำกัดความอย่างเป็นทางการของรูปแบบประเภทนี้ 2) ให้คำจำกัดความอย่างเป็นทางการของการรักษาความปลอดภัยของโครงการ; 3) เพื่อพิสูจน์ความเสถียรของการออกแบบวงจรเฉพาะของประเภทที่กำหนด ที่นี่มีปัญหาหลายอย่างเกิดขึ้นทันที ประการแรกในรูปแบบการเข้ารหัสแน่นอนว่าจะใช้ค่าพารามิเตอร์คงที่เสมอ ตัวอย่างเช่น ระบบการเข้ารหัสลับการเข้ารหัสและทฤษฎีความซับซ้อน 27 ระบบได้รับการออกแบบสำหรับคีย์ที่มีความยาว เช่น 256 หรือ 512 ไบต์ ในการใช้แนวทางความซับซ้อน-ทฤษฎี จำเป็นที่ปัญหาซึ่งควรจะใช้ความซับซ้อนในการคำนวณซึ่งควรจะใช้นั้นต้องมีขนาดใหญ่ ดังนั้นในการเข้ารหัสเชิงทฤษฎี แบบจำลองทางคณิตศาสตร์ของรูปแบบการเข้ารหัสจึงถูกพิจารณา โมเดลเหล่านี้ขึ้นอยู่กับพารามิเตอร์บางตัวที่เรียกว่าพารามิเตอร์ความปลอดภัย ซึ่งสามารถรับค่าขนาดใหญ่ได้ตามอำเภอใจ (โดยปกติ เพื่อความง่าย สันนิษฐานว่าพารามิเตอร์ความปลอดภัยและความปลอดภัยสามารถทำงานบนชุดข้อมูลธรรมชาติทั้งหมด) ประการที่สอง การกำหนดความแข็งแกร่งของรูปแบบการเข้ารหัสขึ้นอยู่กับงานที่ฝ่ายตรงข้ามเผชิญและข้อมูลใดบ้างเกี่ยวกับโครงการที่มีให้สำหรับเขา ดังนั้นความมั่นคงของแผนงานจึงเกิดขึ้น - จำเป็นต้องกำหนดและตรวจสอบแยกกันสำหรับสมมติฐานแต่ละข้อเกี่ยวกับศัตรู ประการที่สาม มีความจำเป็นต้องชี้แจงว่าการคำนวณจำนวนใดที่ถือว่า "ไม่สามารถทำได้ในทางปฏิบัติ" จากข้างต้นพบว่าค่านี้ไม่สามารถเป็นเพียงค่าคงที่ได้ แต่ต้องแสดงด้วยฟังก์ชันของพารามิเตอร์ความปลอดภัยที่เพิ่มขึ้น ตามวิทยานิพนธ์ของ Edmonds อัลกอริธึมถือว่ามีประสิทธิภาพหากเวลาในการดำเนินการถูกจำกัดด้วยพหุนามบางตัวในความยาวของคำที่ป้อน (ในกรณีของเรา อยู่ที่พารามิเตอร์ความปลอดภัย) มิฉะนั้น ว่ากันว่าการคำนวณด้วยอัลกอริธึมนี้แทบจะเป็นไปไม่ได้เลย เรายังทราบด้วยว่าแผนงานการเข้ารหัสลับจะต้องมีประสิทธิภาพ กล่าวคือ การคำนวณทั้งหมดที่กำหนดโดยแผนงานอย่างใดอย่างหนึ่งหรืออย่างอื่นจะต้องดำเนินการในเวลาพหุนาม ประการที่สี่ มีความจำเป็นต้องกำหนดความน่าจะเป็นที่ถือว่าเล็กน้อย ในวิทยาการเข้ารหัส เป็นธรรมเนียมที่จะต้องพิจารณาความน่าจะเป็นที่สำหรับพหุนาม p ใดๆ และสำหรับ n ที่มีขนาดใหญ่เพียงพอจะต้องไม่เกิน 1/p(n) โดยที่ u เป็นพารามิเตอร์ความปลอดภัย ดังนั้น เมื่อมีคำจำกัดความทั้งหมดข้างต้น ปัญหาในการพิสูจน์ความปลอดภัยของรูปแบบการเข้ารหัสจึงลดลงเพื่อพิสูจน์ว่าไม่มีอัลกอริทึมพหุนามที่แก้ปัญหาที่ฝ่ายตรงข้ามเผชิญอยู่ แต่ที่นี่ยังมีอุปสรรคที่ร้ายแรงอีกอย่างหนึ่งเกิดขึ้น: ความทันสมัยทฤษฎีความซับซ้อนในการคำนวณไม่อนุญาตให้พิสูจน์ขอบเขตล่างของ superpolynomial สำหรับความซับซ้อนสำหรับปัญหาเฉพาะของคลาสที่กำลังพิจารณา จากนี้ไปว่าในขณะนี้ความแข็งแกร่งของแผนการเข้ารหัสลับสามารถสร้างขึ้นได้ด้วยการมีส่วนร่วมของสมมติฐานที่ไม่ได้รับการพิสูจน์ ดังนั้น ทิศทางหลักของการวิจัยคือการค้นหาเงื่อนไขที่อ่อนแอที่สุด (ในอุดมคติ จำเป็น และเพียงพอ) สำหรับการดำรงอยู่ของโครงร่างที่มั่นคงของแต่ละประเภท 28 บทที่ 2 โดยทั่วไป พิจารณาสมมติฐานสองประเภท - ทั่วไป (หรือความซับซ้อน-ทฤษฎี) และทฤษฎีจำนวน นั่นคือ สมมติฐานเกี่ยวกับความซับซ้อนของปัญหาทฤษฎีจำนวนเฉพาะ สมมติฐานทั้งหมดเหล่านี้ในวรรณคดีมักเรียกว่าการเข้ารหัส ด้านล่างนี้ เราจะพิจารณาวัตถุทางคณิตศาสตร์ที่น่าสนใจหลายรายการโดยสังเขปที่เกิดขึ้นที่จุดตัดของทฤษฎีความซับซ้อนและการเข้ารหัส มากกว่า ภาพรวมโดยละเอียด เกี่ยวกับปัญหาเหล่านี้สามารถพบได้ในหนังสือ 2. การเข้ารหัสและสมมติฐาน ตามกฎแล้ว ความคุ้นเคยของนักคณิตศาสตร์ที่ไม่เชี่ยวชาญกับทฤษฎีความซับซ้อนในการคำนวณนั้นจำกัดอยู่ที่คลาส P และ NP และการคาดเดาที่มีชื่อเสียง ให้เรานึกถึงข้อมูลที่จำเป็นสั้นๆ จากทฤษฎีความซับซ้อนในการคำนวณ ให้?* เป็นเซตของสตริงจำกัดทั้งหมดในตัวอักษรไบนารี S = (0,1) เซตย่อย L C S* ในทฤษฎีความซับซ้อนมักเรียกว่าภาษา เครื่องจักรทัวริง M ถูกกล่าวว่าทำงานในเวลาพหุนาม (หรือเพียงแค่ว่ามันเป็นพหุนาม) หากมีพหุนาม p เช่นนั้น เมื่อป้อนคำที่มีความยาว n เครื่อง M จะหยุดหลังจากดำเนินการไม่เกิน p(n) . เครื่องทัวริง M รับรู้ (หรือยอมรับ) ภาษา L หากทุกคำที่ป้อน x E L เครื่องจักร M หยุดในสถานะยอมรับ และทุกคำ x $ L ในสถานะปฏิเสธ คลาส P เป็นคลาสของทุกภาษาที่เครื่องจักรทัวริงรู้จักซึ่งทำงานในเวลาพหุนาม ฟังก์ชั่น / : 2* -> 2* สามารถคำนวณได้ในเวลาพหุนามถ้ามีเครื่องพหุนามทัวริงเช่นว่าถ้าคำว่า x E? ภาษา L เป็นของคลาส NP ถ้าภาคแสดง P(x, y) : S* x S* -? (0,1) คำนวณได้ในเวลาพหุนามและพหุนาม p โดยที่ L = (x\3yP(x, y)&i\y\ ^ p(|z|)) ดังนั้น ภาษา L จึงเป็นของ NP ถ้าสำหรับคำใดๆ ใน L ที่มีความยาว n เป็นไปได้ที่จะเดาสตริงของพหุนามความยาวบางส่วนใน n แล้วใช้เพรดิเคต P ตรวจสอบว่าการเดานั้นถูกต้อง เป็นที่ชัดเจนว่า พี ซี เอ็น.พี. การรวมนี้เข้มงวดหรือไม่เป็นหนึ่งในปัญหาที่ยังไม่แก้ที่มีชื่อเสียงที่สุดในวิชาคณิตศาสตร์ ผู้เชี่ยวชาญส่วนใหญ่เชื่อว่าเป็นเรื่องที่เข้มงวด (เรียกว่าสมมติฐาน P^NP) ในคลาส NP คลาสย่อยของภาษาที่ซับซ้อนสูงสุด เรียกว่า NP-complete จะแยกออก: ภาษา NP-complete ใด ๆ จะจดจำได้ในเวลาพหุนามก็ต่อเมื่อ P=NP สำหรับสิ่งต่อไปนี้ เราจะต้องมีแนวคิดเกี่ยวกับเครื่องจักรทัวริงที่น่าจะเป็นไปได้ด้วย ในเครื่องจักรทัวริงธรรมดา (เรียกว่า deterministic-deterministic เพื่อแยกความแตกต่างจากความน่าจะเป็น) สถานะใหม่ที่เครื่องผ่านในขั้นตอนต่อไปจะถูกกำหนดโดยสถานะปัจจุบันและสัญลักษณ์ที่หัวบนเทปคือ กำลังดู ในเครื่องความน่าจะเป็น สถานะใหม่อาจขึ้นอยู่กับตัวแปรสุ่ม ซึ่งใช้ค่า 0 และ 1 โดยมีความน่าจะเป็น 1/2 ต่อแต่ละรายการ อีกทางหนึ่ง ทฤษฎีการเข้ารหัสและความซับซ้อน 29 อาจพิจารณาว่าเครื่องทัวริงความน่าจะเป็นมีเทปสุ่มเพิ่มเติมซึ่งเขียนสตริงสุ่มไบนารีอนันต์ เทปสุ่มสามารถอ่านได้ในทิศทางเดียวเท่านั้น และการเปลี่ยนสถานะใหม่อาจขึ้นอยู่กับตัวละครที่กำลังดูบนเทปนั้น พิจารณาคำถามธรรมดาต่อไปนี้: สมมติฐาน P^NP เป็นเงื่อนไขที่จำเป็นและเพียงพอสำหรับการดำรงอยู่ของแผนการเข้ารหัสที่แข็งแกร่งไม่ใช่หรือ ความจำเป็นในหลายกรณีเกือบจะชัดเจน กลับไปที่ตัวอย่างที่ 1 กำหนดภาษาต่อไปนี้ L = ((Ki,d,i)\ มีข้อความ m เช่น Ek(m) = d และบิตที่ i คือ 1) เป็นที่ชัดเจนว่า L? NP: แทนที่จะค้นหาอย่างละเอียดถี่ถ้วนตามที่อธิบายไว้ในบทนำ คุณสามารถเดาข้อความธรรมดา m แล้วตรวจสอบเวลาพหุนาม-พหุนามที่ Efdim) = d และบิตที่ i m เท่ากับ 1 ถ้าใช่ ให้ป้อนคำที่ป้อน (Ki,d,i) ได้รับการยอมรับ มิฉะนั้นจะถูกปฏิเสธ ภายใต้สมมติฐาน P=NP มีอัลกอริธึมพหุนาม-พหุนามที่กำหนดขึ้นซึ่งรู้จักภาษา L เมื่อรู้ K\ และ d อัลกอริทึมนี้สามารถใช้เพื่อคำนวณข้อความธรรมดา rn ตามลำดับทีละบิต ดังนั้น cryptosystem จึงไม่เสถียร วิธีการเดียวกัน: เดารหัสลับและตรวจสอบ (ในเวลาพหุนาม-พหุนาม) ความถูกต้องของการเดานั้นใช้ได้กับแผนการเข้ารหัสอื่น ๆ อย่างไรก็ตาม ในบางกรณี ปัญหาทางเทคนิคเกิดขึ้นเนื่องจากข้อเท็จจริงที่ว่า ตามข้อมูลที่ฝ่ายตรงข้ามมี ค่าที่ต้องการ (ข้อความธรรมดา คีย์ลับ ฯลฯ) ไม่ได้รับการคืนค่าโดยเฉพาะ สำหรับคำถามเกี่ยวกับความเพียงพอของสมมติฐาน P^NP แนวทางต่อไปนี้แนะนำตัวเองที่นี่: เลือกปัญหา NP-complete และสร้างบนพื้นฐานของรูปแบบการเข้ารหัสที่มีปัญหาแตกหัก (เช่น ปัญหาที่ฝ่ายตรงข้ามเผชิญอยู่) จะเป็น NP -เต็ม. ความพยายามดังกล่าวเกิดขึ้นในช่วงต้นทศวรรษ 1980 โดยเฉพาะอย่างยิ่งในความสัมพันธ์กับระบบเข้ารหัสคีย์สาธารณะ แต่ไม่ได้นำไปสู่ความสำเร็จ ผลลัพธ์ของความพยายามทั้งหมดเหล่านี้คือการตระหนักถึงข้อเท็จจริงต่อไปนี้: แม้ว่า P^NP ปัญหาใดๆ ของ NP-complete อาจกลายเป็นเรื่องยากในลำดับอนันต์ของคำอินพุตบางลำดับเท่านั้น กล่าวอีกนัยหนึ่ง คำจำกัดความของคลาส NP รวมถึงการวัดความซับซ้อน "กรณีที่แย่ที่สุด" เพื่อความเสถียรของรูปแบบการเข้ารหัสลับ จำเป็นที่ปัญหาของคู่ต่อสู้จะยาก "เกือบทุกที่" ดังนั้นจึงเป็นที่ชัดเจนว่าจำเป็นต้องมีการสันนิษฐานที่แข็งแกร่งกว่า P^NP สำหรับการรักษาความปลอดภัยการเข้ารหัส กล่าวคือสมมติฐานของการมีอยู่ของฟังก์ชันทางเดียว 30 บทที่ 2 3. ฟังก์ชันทางเดียว พูดอย่างไม่เป็นทางการว่า ฟังก์ชันทางเดียวคือฟังก์ชันที่คำนวณได้อย่างมีประสิทธิภาพ ซึ่งไม่มีอัลกอริธึมที่มีประสิทธิภาพที่จะกลับด้าน โดยการผกผันเราหมายถึงปัญหาใหญ่ในการค้นหาจากค่าที่กำหนดของฟังก์ชันค่าหนึ่ง (lu- (ใดๆ) จาก preimage (โปรดทราบว่าฟังก์ชันผกผันโดยทั่วไปอาจไม่มีอยู่) เนื่องจากแนวคิดของ ฟังก์ชันทางเป็นศูนย์กลางในการเข้ารหัสทางคณิตศาสตร์ ด้านล่าง เราจะให้คำจำกัดความอย่างเป็นทางการ ให้ E™ = (0,1)" เป็นเซตของสตริงไบนารีทั้งหมดที่มีความยาว n โดยฟังก์ชัน / เราหมายถึงตระกูล (/n) โดยที่ /" : E" -> Em, m = m,( n) เพื่อความง่าย เราคิดว่า n จะวิ่งผ่านอนุกรมธรรมชาติทั้งหมด และแต่ละฟังก์ชัน /n ถูกกำหนดไว้ทุกที่ ฟังก์ชัน / ถูกกล่าวว่าซื่อสัตย์ หากมีพหุนาม q ซึ่ง n $ C q(m(n)) สำหรับ n คำจำกัดความทั้งหมด 1. ฟังก์ชันที่ซื่อสัตย์ / เรียกว่าเป็นด้านเดียวถ้า 1. มีอัลกอริทึมพหุนามที่คำนวณ f(x) สำหรับ x 2 ใด ๆ สำหรับเครื่องทัวริงพหุนามความน่าจะเป็นใด ๆ ต่อไปนี้ถือ: ให้สุ่มเลือกสตริง x จากชุด E" (แสดง x € q X ") จากนั้นสำหรับใด ๆ th พหุนาม p และทั้งหมดมีขนาดใหญ่เพียงพอ n Pr(f(A(f(x))) = /(*))< l/p(n). Вероятность здесь определяется случайным выбором строки х и слу- случайными величинами, которые А использует в своей работе. Условие 2 качественно означает следующее. Любая полиномиальная вероятностная машина Тьюринга А может по данному у найти х из уравнения f(x) = у лишь с пренебрежимо малой вероятностью. Заметим, что требование честности нельзя опустить. Поскольку длина входного слова f(x) машины А равна т, ей может не хватить полиномиального (от т) времени просто на выписывание строки х, ес- если / слишком сильно «сжимает» входные значения. Ясно, что из предположения о существовании односторонних функ- функций следует, что P^NP. Однако, не исключена следующая ситуация: P^NP, но односторонних функций нет. Существование односторонних функций является необходимым ус- условием для стойкости многих типов криптографических схем. В неко- некоторых случаях этот факт устанавливается достаточно просто. Обра- Обратимся опять к примеру 1. Рассмотрим функцию / такую, что /(г) = К\. Она вычислима с помощью алгоритма G за полиномиальное время. По- Покажем, что если / - не односторонняя функция, то криптосистема Криптография и теория сложности 31 нестойкая. Предположим, что существует полиномиальный вероятност- вероятностный алгоритм Л, который инвертирует / с вероятностью по крайней мере 1/р(п) для некоторого полинома р. Здесь п - длина ключа К\. Противник может подать на вход алгоритму А ключ К\ и получить с указанной вероятностью некоторое значение г" из прообраза. Далее противник подает г" на вход алгоритма G и получает пару ключей (Ki,K2). Хотя К2 не обязательно совпадает с К^, тем не менее, по определению криптосистемы DK* {Екг (тп)) = m для любого открытого текста т. Поскольку К2 найден с вероятностью по крайней мере 1/р(п), которая в криптографии не считается пренебрежимо малой, криптоси- криптосистема нестойкая. Для других криптографических схем подобный результат доказы- доказывается не столь просто. В работе Импальяццо и Луби доказана не- необходимость односторонних функций для существования целого ряда стойких криптографических схем. Из всего сказанного следует, что предположение о существова- существовании односторонних функций является самым слабым криптографи- криптографическим предположением, которое может оказаться достаточным для доказательства существования стойких криптографических схем раз- различных типов. На выяснение того, является ли это условие и в са- самом деле достаточным, направлены значительные усилия специалистов. Трудность задачи построения криптографических схем из односто- односторонних функций можно пояснить на следующем примере. Пусть / - односторонняя функция и нам требуется построить криптосистему с секретным ключом. В такой криптосистеме имеется только один ключ - секретный, который известен и отправителю, и получателю шифрованного сообщения. Алгоритмы шифрования Ец и дешифро- дешифрования Dk оба зависят от этого секретного ключа К и таковы, что Dk(Ek(tti)) = т для любого открытого текста т. Ясно, что если кри- криптограмму d сообщения т вычислять как d = /(m), то противник, перехвативший d, может вычислить m лишь с пренебрежимо малой вероятностью. Но во-первых, непонятно, каким образом сможет вос- восстановить сообщение m из криптограммы законный получатель? Во- вторых, из того, что функция / односторонняя следует лишь, что про- противник не может вычислить все сообщение целиком. А это - весьма низкий уровень стойкости. Желательно, чтобы противник, знающий криптограмму d, не мог вычислить ни одного бита открытого тек- текста. На ช่วงเวลานี้ ได้รับการพิสูจน์แล้วว่าการมีอยู่ของฟังก์ชันทางเดียวเป็นเงื่อนไขที่จำเป็นและเพียงพอสำหรับการมีอยู่ของระบบเข้ารหัสลับที่แข็งแกร่งด้วยคีย์ลับ เช่นเดียวกับโปรโตคอลการเข้ารหัสที่แข็งแกร่งหลายประเภท รวมถึงโปรโปรโตคอลลายเซ็นอิเล็กทรอนิกส์ ในทางกลับกัน มีผลลัพธ์จาก Impagliazzo และ Rudich ซึ่งเป็นข้อโต้แย้งที่ค่อนข้างชัดเจนว่ารูปแบบการเข้ารหัสลับบางประเภท (รวมถึงโปรโตคอลการกระจายคีย์ประเภท Diffie-Hellman) ต้องการสมมติฐานที่แข็งแกร่งกว่าที่คาดไว้ การมีอยู่ของฟังก์ชันทางเดียว ขออภัย ผลลัพธ์นี้ซับซ้อนเกินกว่าจะอธิบายในบทนี้ 4. เครื่องกำเนิดแบบสุ่มหลอก ข้อเสียเปรียบที่สำคัญของรหัส Vernam คือกุญแจเป็นแบบครั้งเดียว เป็นไปได้ไหมที่จะกำจัดข้อเสียนี้โดยลดความทนทานลงเล็กน้อย? วิธีหนึ่งในการแก้ปัญหาการทดลองใช้นี้มีดังนี้ ผู้ส่งและผู้รับมีคีย์ลับร่วมกัน K ที่มีความยาว n และด้วยความช่วยเหลือของอัลกอริธึม q ที่มีประสิทธิภาพเพียงพอ พวกเขาสร้างลำดับจากมัน r - q(K) ของความยาว q(n) โดยที่ q คือพหุนามบางตัว crypto-cryptosystem ดังกล่าว (เราแสดงว่า C r) อนุญาตให้คุณเข้ารหัสข้อความ m (หรือชุดข้อความ) สูงสุด q (n) บิตในความยาวตามสูตร d - r (B ใน โดยที่ © เป็นบิต การเพิ่มสตริงบิต modulo 2 Deshi- ถอดรหัสจะดำเนินการตามสูตร m = d φ r จากผลลัพธ์ของ Shanno-Shannon ที่ระบบเข้ารหัสดังกล่าวไม่ปลอดภัยอย่างแน่นอน กล่าวคือ ป้องกันศัตรู (ซึ่งอย่างไรก็ตาม ไม่ยากที่จะตรวจสอบโดยตรง) จะเกิดอะไรขึ้นหากจำเป็นต้องป้องกันเฉพาะกับคู่อริที่มีพหุนามจำกัดซึ่งสามารถโจมตีระบบเข้ารหัสลับได้ด้วยความช่วยเหลือของอัลกอริธึมความน่าจะเป็นพหุนามพหุนามเท่านั้นคำถามเหล่านี้นำไปสู่แนวคิดของตัวสร้างสุ่มหลอก ซึ่ง Blum และ Micali แนะนำ ให้ q: (0,1) "-" (0,1)? n" เป็นฟังก์ชันที่คำนวณได้ในพหุนาม (จาก พี) เวลา ฟังก์ชันดังกล่าวเรียกว่าเครื่องกำเนิด ตามสัญชาตญาณแล้ว ตัวสร้าง q จะเป็นแบบสุ่มหลอก ถ้าลำดับที่สร้างขึ้นโดยลำดับนั้นแยกไม่ออกจากอัลกอริธึม ve-probabilistic ของพหุนามจากลำดับสุ่มที่มีความยาวเท่ากัน q(n) อย่างเป็นทางการ วัตถุนี้ถูกกำหนดดังนี้ ให้ A เป็นเครื่องทัวริงความน่าจะเป็นพหุนามที่ได้รับสตริงไบนารีที่มีความยาว q(n) เป็นอินพุตและเอาต์พุตหนึ่งบิตอันเป็นผลมาจากการดำเนินการ ให้ P(A, n) = Pr(A(r) = 1|r unit (0, Cryptography and Complexity Theory 33) ความน่าจะเป็นที่นี่ถูกกำหนดโดยการสุ่มเลือกสตริง r และตัวแปรสุ่มที่ A ใช้ใน ทำงาน ให้ P2 (A,n) = Pr(A(g(s)) = l|e หน่วย (0,1)") ความน่าจะเป็นนี้พิจารณาจากการสุ่มเลือกแถว s และตัวแปรสุ่มที่ A ใช้ในงานของเขา เราเน้นว่าฟังก์ชัน g ถูกคำนวณโดยอัลกอริธึมที่กำหนดขึ้นเอง คำจำกัดความ 2 ตัวสร้าง g ถูกเรียกว่าตัวสร้างสุ่มเทียมแบบเข้ารหัสที่มีความปลอดภัยหากสำหรับเครื่องทัวริงพหุนามที่น่าจะเป็นพหุนามใด ๆ สำหรับพหุนาม p ใด ๆ และทั้งหมดมีขนาดใหญ่เพียงพอ n \P,(A,n)-P2 (A, p)\<1/р(п). Всюду ниже мы для краткости будем называть криптографически стойкие псевдослучайные генераторы просто псевдослучайными гене- генераторами. Такое сокращение является общепринятым в криптографи- криптографической литературе. Нетрудно убедиться, что для существования псевдослучайных гене- генераторов необходимо существование односторонних функций. В самом деле, сама функция g должна быть односторонней. Доказательство это- этого простого факта мы оставляем читателю в качестве упражнения. Вопрос о том, является ли существование односторонних функций од- одновременно и достаточным условием, долгое время оставался откры- открытым. В 1982 г. Яо построил псевдослучайный генератор, исходя из предположения о существовании односторонних перестановок, т. е. сохраняющих длину взаимнооднозначных односторонних функций. За этим последовала серия работ, в которых достаточное условие все более и более ослаблялось, пока наконец в 1989-1990 гг. Импальяццо, Левин и Луби и Хостад не получили следующий окончательный резуль- результат. Теорема 1. Псевдослучайные генераторы существуют тогда и толь- только тогда, когда существуют односторонние функции. Псевдослучайные генераторы находят применение не только в крип- криптографии, но и в теории сложности, и в других областях дискретной математики. Обсуждение этих приложений выходит за рамки настоя- настоящей главы. Здесь же в качестве иллюстрации мы рассмотрим описан- описанную в начале данного раздела криптосистему Сг, использующую псев- псевдослучайный генератор в качестве алгоритма д. Прежде всего, нам необходимо дать определение стойкости криптосистемы с секретным ключом. Пусть Ец - алгоритм шифрования криптосистемы с секретным ключом. Обозначим результат его работы d = Ек(т), здесь К - се- секретный ключ длиной п битов, am - открытый текст длиной q(n) 34 Глава 2 битов. Через т* обозначается г-ый бит открытого текста. Пусть А - полиномиальная вероятностная машина Тьюринга, которая получает на вход криптограмму d и выдает пару (г,сг), где г б {1,.. .,q(n)}, а б {0,1}. Интуитивно, криптосистема является стойкой, если ника- никакая машина Тьюринга А не может вычислить ни один бит открытого текста с вероятностью успеха, существенно большей, чем при простом угадывании. Определение 3. Криптосистема называется стойкой, если для лю- любой полиномиальной вероятностной машины Тьюринга А, для любого полинома р и всех достаточно больших п Pr{A(d) = (г,а)ка = пц\Кен {0,1}", т 6д {0,1}*<п)} < J + ~. 2 р(п) Эта вероятность (всюду ниже для краткости мы ее обозначаем про- просто Рг) определяется случайным выбором секретного ключа К, слу- случайным выбором открытого текста т из множества всех двоичных строк длины q(n) и случайными величинами, которые А использует в своей работе. Покажем, что криптосистема Сг с псевдослучайным генератором в качестве д является стойкой в смысле данного определения. Предполо- Предположим противное, т. е. что существуют полиномиальный вероятностный алгоритм А и полином р такие, что Рг ^ 1/2 + 1/р(п) для бесконечно многих п. Рассмотрим алгоритм В, который получает на входе двоич- двоичную строку г длины 0, q - จากเซตของตัวหารเฉพาะของจำนวน p - 1, q - จากเซตของตัวเลขทั้งหมด q ที่ q9 = 1 mod p และ x ∈ Zg จากนั้นฟังก์ชัน f(x, p, q, g) = (gx mod p, p, q, q) เป็นฟังก์ชันทางเดียว (ดูบทที่ 2) ที่แนะนำ

หนังสือ. ดาวน์โหลดหนังสือ DJVU, PDF ฟรี ห้องสมุดอิเล็กทรอนิกส์ฟรี
วี.วี. Yashchenko ความรู้เบื้องต้นเกี่ยวกับการเข้ารหัส

คุณสามารถ (โปรแกรมจะทำเครื่องหมายเป็นสีเหลือง)
คุณสามารถดูรายชื่อหนังสือเกี่ยวกับคณิตศาสตร์ชั้นสูงที่เรียงตามตัวอักษร
คุณสามารถดูรายชื่อหนังสือเกี่ยวกับฟิสิกส์ระดับสูงที่เรียงตามตัวอักษรได้

• ดาวน์โหลดหนังสือฟรี, ปริมาณ 1.69 Mb, รูปแบบ .djvu
รุ่นที่สอง, ed. Yashchenko V.V., กันยายน 1999

สุภาพสตรีและสุภาพบุรุษ!! ในการดาวน์โหลดไฟล์สิ่งพิมพ์อิเล็กทรอนิกส์โดยไม่มี "ข้อบกพร่อง" ให้คลิกที่ลิงก์ที่ขีดเส้นใต้พร้อมกับไฟล์ ปุ่มเมาส์ขวา, เลือกคำสั่ง "บันทึกเป้าหมายเป็น ... " ("บันทึกเป้าหมายเป็น...") และบันทึกไฟล์ e-pub ลงในเครื่องคอมพิวเตอร์ของคุณ สิ่งพิมพ์อิเล็กทรอนิกส์มักอยู่ในรูปแบบ Adobe PDF และ DJVU

บทที่ 1 แนวคิดพื้นฐานของการเข้ารหัส
1. บทนำ
2. เรื่องของการเข้ารหัส
3. พื้นฐานทางคณิตศาสตร์
4. ทิศทางใหม่
5. สรุป

บทที่ 2 ทฤษฎีการเข้ารหัสและความซับซ้อน
1. บทนำ
2. การเข้ารหัสและสมมติฐาน
3. ฟังก์ชั่นทางเดียว
4. เครื่องกำเนิดสุ่มเทียม
5. การพิสูจน์ความรู้ที่เป็นศูนย์

บทที่ 3 โปรโตคอลการเข้ารหัส
1. บทนำ
2. ความซื่อสัตย์ โปรโตคอลการตรวจสอบสิทธิ์และลายเซ็นอิเล็กทรอนิกส์
3. ไม่สามารถติดตามได้ เงินอิเล็กทรอนิกส์
4. โปรโตคอลเช่น "โยนเหรียญบนโทรศัพท์"
5. อีกครั้งเกี่ยวกับการแบ่งปันความลับ
6. มาเล่น "ถ้วย" กันเถอะ ระเบียบการลงคะแนนเสียง
7. เหนือกว่าสมมติฐานมาตรฐาน ข้อความลับ
8. แทนที่จะเป็นข้อสรุป

บทที่ 4
1. บทนำ
2. ระบบเข้ารหัส RSA
3. ความซับซ้อนของอัลกอริธึมเชิงตัวเลข
4. วิธีแยกแยะจำนวนประกอบจากจำนวนเฉพาะ
5. วิธีสร้างไพรม์ขนาดใหญ่
6. วิธีทดสอบจำนวนมากสำหรับความเป็นปฐมภูมิ
7. วิธีแยกตัวประกอบตัวเลขประกอบ
8. ลอการิทึมแบบไม่ต่อเนื่อง
9. บทสรุป

บทที่ 5 คณิตศาสตร์ของการแบ่งปันความลับ
1. บทนำ
2. การแบ่งปันความลับสำหรับโครงสร้างการเข้าถึงโดยพลการ
3. การแบ่งปันความลับเชิงเส้น
4. การแบ่งปันความลับที่สมบูรณ์แบบและเมทรอยด์

บทที่ 6
1. แทนการแนะนำตัว
2. ทฤษฎีเล็กน้อย
3. จะเข้ารหัสไฟล์ได้อย่างไร?
4. เรียนรู้จากความผิดพลาดของผู้อื่น
5. แทนที่จะเป็นข้อสรุป

บทที่ 7
1. บทนำ
2. รหัสทดแทน
3. รหัสการเรียงสับเปลี่ยน
4. รหัสแทนที่ Polyalphabetic ด้วยคีย์เป็นระยะ
5. เงื่อนไขปัญหาการแข่งขันกีฬาโอลิมปิกในวิชาคณิตศาสตร์และการเข้ารหัส
6. ทิศทางและการตัดสินใจ

ภาคผนวก: ข้อความที่ตัดตอนมาจากบทความโดย K. Shannon "ทฤษฎีการสื่อสารในระบบลับ"

บทสรุปสั้น ๆ ของหนังสือ

ต่ำกว่าทั้งหมด เอ็ด VVYashchenko ผู้แต่ง: V. V. Yashchenko (บรรณาธิการ บทที่ 1), N. P. Varnovsky (บทที่ 2, 3), Yu. V. Nesterenko (บทที่ 4), G. A. Kabatyansky (บทที่ 5), P. N Devyanin, V. G. Proskurin, A. V. Cheremushkin (บทที่ 6) ), P. A. Gyrdymov, A. Yu. Zubov, A. V. Zyazin, V. N. Ovchinnikov (บทที่ 7)

เป็นครั้งแรกในภาษารัสเซีย หนังสือเล่มนี้ได้นำเสนอการนำเสนออย่างเป็นระบบเกี่ยวกับพื้นฐานทางวิทยาศาสตร์ของการเข้ารหัสตั้งแต่ตัวอย่างที่ง่ายที่สุดและแนวคิดพื้นฐานไปจนถึงการสร้างการเข้ารหัสที่ทันสมัย การทำความเข้าใจหลักการของการเข้ารหัสกลายเป็นสิ่งจำเป็นสำหรับหลาย ๆ คนเนื่องจากการใช้เครื่องมือรักษาความปลอดภัยข้อมูลการเข้ารหัสอย่างแพร่หลาย ดังนั้นหนังสือเล่มนี้จึงมีประโยชน์ต่อผู้อ่านทั่วไป หนังสือเล่มนี้มีไว้สำหรับนักเรียนของคณิตศาสตร์และผู้เชี่ยวชาญด้านความปลอดภัยของข้อมูล

การเข้ารหัส - ศาสตร์แห่งการเข้ารหัส - ถูกจัดประเภทมาเป็นเวลานาน เนื่องจากส่วนใหญ่ใช้เพื่อปกป้องความลับของรัฐและทางการทหาร ปัจจุบันมีการใช้วิธีการและวิธีการเข้ารหัสเพื่อรับรองความปลอดภัยของข้อมูลไม่เพียง แต่ของรัฐเท่านั้น แต่ยังรวมถึงบุคคลและองค์กรด้วย นี้ไม่จำเป็นต้องเป็นเรื่องของความลับ ข้อมูลที่แตกต่างกันมากเกินไป "เดิน" ไปทั่วโลกในรูปแบบดิจิทัล และเหนือข้อมูลนี้มีภัยคุกคามจากการรู้จักที่ไม่เป็นมิตร การสะสม การทดแทน การปลอมแปลง ฯลฯ เป็นการเข้ารหัสที่ให้วิธีการที่เชื่อถือได้มากที่สุดในการป้องกันภัยคุกคามดังกล่าว

จนถึงตอนนี้ อัลกอริธึมการเข้ารหัสสำหรับผู้บริโภคทั่วไปเป็นความลับโดยมีตราประทับเจ็ดดวง แม้ว่าหลายคนเคยใช้เครื่องมือเข้ารหัสลับบางอย่างแล้ว: การเข้ารหัสอีเมล บัตรธนาคารอัจฉริยะ ฯลฯ โดยธรรมชาติแล้ว คำถามหลักสำหรับผู้ใช้ก็คือว่าเครื่องมือเข้ารหัสลับนี้มีให้หรือไม่ การป้องกันที่เชื่อถือได้ แต่การกำหนดคำถามเบื้องต้นนี้ให้ถูกต้องไม่ใช่เรื่องง่าย เรากำลังป้องกันศัตรูตัวใดอยู่? อะไรคือตัวเลือกสำหรับศัตรูตัวนี้? เขาสามารถบรรลุเป้าหมายอะไรได้บ้าง? จะวัดความน่าเชื่อถือของการป้องกันได้อย่างไร? รายการคำถามดังกล่าวสามารถดำเนินการต่อได้ ในการตอบคำถาม ผู้ใช้ต้องการความรู้เกี่ยวกับแนวคิดพื้นฐานของการเข้ารหัส

นิทรรศการที่เป็นที่นิยมของพื้นฐานทางวิทยาศาสตร์ของการเข้ารหัส (เรากำลังพูดถึงเฉพาะการเข้ารหัส "ที่ไม่ใช่ของรัฐ" ส่วนของการเข้ารหัสที่เกี่ยวข้องกับความมั่นคงของรัฐควรเป็นความลับ) เป็นเป้าหมายของหนังสือเล่มนี้ ยังสามารถใช้เป็นสื่อการสอนได้อีกด้วย ยังไม่มีหนังสือที่คล้ายกันในภาษารัสเซีย เนื้อหาของบทจำนวนหนึ่งเผยแพร่โดยผู้เขียนก่อนหน้านี้ในสิ่งพิมพ์อื่น ๆ (บทที่ 1 - ในหนังสือโดย S. A. Dorichenko, V. V. Yashchenko, "25 Studies on ciphers", M.: TEIS, 1994; ตอนที่ 1,2,4 ,5 - ในวารสาร "Mathematical Education", ชุดที่สาม, ฉบับที่ 2, M.: MTsNMO, 1998; บทที่ 7 - ในหนังสือพิมพ์ "Informatika" (ภาคผนวกรายสัปดาห์ของหนังสือพิมพ์ "Pervoe september"), N 4, มกราคม 1998 ). ในการเตรียมฉบับนี้ เอกสารเหล่านี้ได้รับการแก้ไขและเพิ่มเติม การนำเสนอเนื้อหาได้รับการออกแบบสำหรับผู้อ่านที่มีความคิดทางคณิตศาสตร์

โดยส่วนใหญ่แล้ว บทต่างๆ จะเป็นอิสระจากกัน (สามารถทำได้ผ่านการทำซ้ำบางส่วน) และสามารถอ่านได้ในลำดับใดก็ได้ บทที่ 1 - เกริ่นนำ - แนะนำให้ทุกคนอ่าน เนื่องจากจะอธิบายแนวคิดพื้นฐานทั้งหมดของการเข้ารหัสสมัยใหม่ในระดับที่นิยม: รหัส คีย์ ความปลอดภัย ลายเซ็นดิจิทัลอิเล็กทรอนิกส์ โปรโตคอลการเข้ารหัส ฯลฯ ในบทอื่น ๆ ส่วนหนึ่งของเนื้อหา ซ้ำแล้วซ้ำเล่าแต่ในเชิงลึกยิ่งขึ้น บทที่ 2, 3, 4, 5 ใช้ข้อมูลบางส่วนจากคณิตศาสตร์ชั้นสูงที่นักเรียนในชั้นเรียนคณิตศาสตร์และนักเรียนรู้จัก บทที่ 6 มุ่งเป้าไปที่ผู้เชี่ยวชาญด้านเทคโนโลยีคอมพิวเตอร์ บทที่ 7 มีเนื้อหาสำหรับการเข้ารหัสโอลิมปิกสำหรับเด็กนักเรียนดังนั้นจึงไม่จำเป็นต้องอ่านความรู้นอกเหนือจากหลักสูตรของโรงเรียน

คำเตือน: เครื่องมือเข้ารหัสและผลิตภัณฑ์ซอฟต์แวร์ที่กล่าวถึงในหนังสือเล่มนี้ใช้เพื่อแสดงแนวคิดทั่วไปเกี่ยวกับการเข้ารหัสเท่านั้น ผู้เขียนไม่ได้ตั้งเป้าที่จะประเมินหรือเปรียบเทียบเครื่องมือเข้ารหัสที่มีอยู่ในตลาด

การเข้ารหัสถูกวางบนพื้นฐานทางวิทยาศาสตร์ส่วนใหญ่มาจากการทำงานของนักวิทยาศาสตร์ชาวอเมริกันที่โดดเด่น Claude Shannon รายงานของเขาเรื่อง "Mathematical Theory of Cryptography" จัดทำขึ้นอย่างลับๆ ในปี 1945 ยกเลิกการจัดประเภทและตีพิมพ์ในปี 1948 แปลเป็นภาษารัสเซียในปี 1963 เนื่องจาก "Works on Information Theory and Cybernetics" (1963) โดย C. Shannon กลายเป็นหนังสือที่หายากทางบรรณานุกรม เราจึงรวมเอา ในภาคผนวกส่วนหลักของบทความโดย K. Shannon "ทฤษฎีการสื่อสารในระบบลับ" ขอแนะนำให้อ่านงานน้ำเชื้อนี้สำหรับผู้ที่สนใจในการเข้ารหัส

เพื่อความเข้าใจอย่างมืออาชีพเกี่ยวกับอัลกอริธึมการเข้ารหัสและความสามารถในการประเมินจุดแข็งและจุดอ่อน จำเป็นต้องมีการฝึกอบรมทางคณิตศาสตร์อย่างจริงจัง (ในระดับแผนกคณิตศาสตร์ของมหาวิทยาลัย) เนื่องจากวิทยาการเข้ารหัสลับสมัยใหม่มีพื้นฐานมาจากผลลัพธ์เชิงลึกของสาขาคณิตศาสตร์ เช่น ทฤษฎีความซับซ้อนของการคำนวณ ทฤษฎีจำนวน พีชคณิต ทฤษฎีสารสนเทศ เป็นต้น ผู้ที่ต้องการศึกษาวิทยาการเข้ารหัสลับอย่างจริงจังสามารถแนะนำเอกสารทบทวนได้ "การเข้ารหัสในการธนาคาร" โดย Anokhin M. I. , Varnovsky N. P. , Sidelnikova V. M. , Yashchenko V. V. , M.: MEPhI, 1997

จะถ่ายโอนข้อมูลที่จำเป็นไปยังผู้รับที่จำเป็นอย่างเป็นความลับจากผู้อื่นได้อย่างไร? ผู้อ่านแต่ละคนในช่วงเวลาที่แตกต่างกันและมีเป้าหมายที่แตกต่างกันอาจพยายามแก้ปัญหาในทางปฏิบัตินี้ด้วยตนเอง (เพื่อความสะดวกในการอ้างอิงเพิ่มเติม เราจะเรียกสิ่งนี้ว่า "ปัญหา TP" นั่นคือปัญหาของการส่งข้อมูลลับ) เมื่อเลือกวิธีแก้ปัญหาที่เหมาะสมแล้ว เขามักจะคิดค้นวิธีการส่งข้อมูลอย่างลับๆ ซ้ำๆ ซึ่งมีอายุมากกว่าหนึ่งพันปีแล้ว

เมื่อพิจารณาถึงปัญหา TP แล้ว ไม่ยากเลยที่จะสรุปว่ามีความเป็นไปได้สามประการ
1. สร้างช่องทางการสื่อสารที่เชื่อถือได้อย่างแท้จริงระหว่างสมาชิกซึ่งไม่สามารถเข้าถึงได้สำหรับผู้อื่น
2. ใช้ช่องทางการสื่อสารสาธารณะ แต่ปิดบังความจริงของการถ่ายโอนข้อมูล
3. ใช้ช่องทางการสื่อสารสาธารณะ แต่ส่งข้อมูลที่จำเป็นผ่านช่องทางดังกล่าวในรูปแบบที่เปลี่ยนแปลงซึ่งมีเพียงผู้รับเท่านั้นที่สามารถกู้คืนได้

ให้ความเห็นเกี่ยวกับความเป็นไปได้ทั้งสามนี้
1. ด้วยระดับการพัฒนาวิทยาศาสตร์และเทคโนโลยีในปัจจุบัน แทบจะเป็นไปไม่ได้เลยที่จะสร้างช่องทางการสื่อสารระหว่างสมาชิกระยะไกลสำหรับการส่งข้อมูลจำนวนมากซ้ำๆ
2. Steganography มีส่วนร่วมในการพัฒนาวิธีการและวิธีการซ่อนความจริงของการส่งข้อความ

ร่องรอยแรกของวิธีการสเตกาโนกราฟีสูญหายไปในสมัยโบราณ ตัวอย่างเช่นรู้จักวิธีการซ่อนข้อความที่เป็นลายลักษณ์อักษร: โกนศีรษะของทาสเขียนข้อความบนหนังศีรษะและหลังจากที่ผมงอกขึ้นใหม่ทาสก็ถูกส่งไปยังผู้รับ จากงานนักสืบ วิธีการต่างๆ ของการเขียนลับระหว่างบรรทัดของข้อความธรรมดาที่ไม่มีการป้องกันเป็นที่รู้จักกันดี: ตั้งแต่นมไปจนถึงสารเคมีที่ซับซ้อนพร้อมการประมวลผลที่ตามมา

วิธี "microdot" เป็นที่รู้จักกันจากนักสืบเช่นกัน: ข้อความถูกบันทึกโดยใช้เทคโนโลยีที่ทันสมัยบนสื่อขนาดเล็กมาก (microdot) ซึ่งส่งด้วยจดหมายธรรมดาเช่นภายใต้ตราประทับหรือที่อื่น ๆ ที่กำหนดไว้ล่วงหน้า

ในปัจจุบัน เนื่องจากการใช้คอมพิวเตอร์อย่างแพร่หลาย จึงมีวิธีการอันละเอียดอ่อนหลายอย่างในการ "ซ่อน" ข้อมูลที่ได้รับการป้องกันไว้ภายในข้อมูลจำนวนมากที่จัดเก็บไว้ในคอมพิวเตอร์ ตัวอย่างของการซ่อนไฟล์ข้อความในกราฟิกสามารถพบได้บนอินเทอร์เน็ต มันยังได้รับในนิตยสาร Computerra, N48 (225) ของวันที่ 1 ธันวาคม 1997 ในหน้า 62 (ควรสังเกตว่าผู้เขียนบทความในนิตยสารอ้างถึง steganography กับการเข้ารหัสอย่างไม่ถูกต้อง ข้อความ แต่โดยทั่วไปแล้ว steganography และ cryptography เป็นพื้นที่ที่แตกต่างกันโดยพื้นฐานในทฤษฎีและการปฏิบัติด้านความปลอดภัยของข้อมูล)

3. การเข้ารหัสลับมีส่วนร่วมในการพัฒนาวิธีการแปลงข้อมูล (เข้ารหัส) เพื่อปกป้องข้อมูลจากผู้ใช้ที่ผิดกฎหมาย วิธีการและวิธีการแปลงข้อมูลดังกล่าวเรียกว่ารหัสลับ

การเข้ารหัส (encryption) เป็นกระบวนการของการใช้รหัสลับกับข้อมูลที่ได้รับการป้องกัน เช่น การแปลงข้อมูลที่ได้รับการป้องกัน (ข้อความธรรมดา) เป็นข้อความที่เข้ารหัส (ข้อความเข้ารหัส การเข้ารหัส) โดยใช้กฎบางอย่างที่อยู่ในรหัส

การถอดรหัสเป็นกระบวนการที่ตรงกันข้ามกับการเข้ารหัส กล่าวคือ การแปลงข้อความที่เข้ารหัสเป็นข้อมูลที่ได้รับการป้องกันโดยใช้กฎบางอย่างที่มีอยู่ในรหัส

การเข้ารหัสเป็นวิทยาศาสตร์ประยุกต์ มันใช้ความสำเร็จล่าสุดของวิทยาศาสตร์พื้นฐานและประการแรกคือคณิตศาสตร์ ในทางกลับกัน งานเฉพาะทั้งหมดของการเข้ารหัสนั้นขึ้นอยู่กับระดับของการพัฒนาเทคโนโลยีและเทคโนโลยีเป็นหลัก โดยขึ้นอยู่กับวิธีการสื่อสารที่ใช้และวิธีการส่งข้อมูล

เรื่องของการเข้ารหัส หัวข้อของการเข้ารหัสคืออะไร? เพื่อตอบคำถามนี้ ให้เรากลับไปที่ปัญหา TP เพื่อชี้แจงสถานการณ์และแนวคิดที่ใช้ ก่อนอื่น เราทราบว่าปัญหานี้เกิดขึ้นเฉพาะกับข้อมูลที่ต้องการการป้องกันเท่านั้น โดยปกติในกรณีดังกล่าว จะมีการกล่าวว่าข้อมูลมีความลับหรือได้รับการคุ้มครอง เป็นส่วนตัว เป็นความลับ เป็นความลับ สำหรับสถานการณ์ทั่วไปที่พบได้บ่อยในประเภทนี้ แม้แต่แนวคิดพิเศษก็ได้รับการแนะนำ:
- ความลับของรัฐ
- ความลับทางการทหาร
- ความลับทางการค้า;
- ความลับทางกฎหมาย
- ความลับทางการแพทย์ ฯลฯ

นอกจากนี้ เราจะพูดถึงข้อมูลที่ได้รับการคุ้มครอง โดยคำนึงถึงคุณลักษณะต่อไปนี้ของข้อมูลดังกล่าว:
- มีผู้ใช้ที่ถูกต้องตามกฎหมายบางกลุ่มที่มีสิทธิ์เป็นเจ้าของข้อมูลนี้
- มีผู้ใช้ที่ผิดกฎหมายที่ต้องการรับข้อมูลนี้เพื่อนำไปใช้เพื่อประโยชน์ของตนเองและเพื่อความเสียหายต่อผู้ใช้ที่ถูกต้องตามกฎหมาย

หนังสือ ดาวน์โหลดหนังสือ ดาวน์โหลดหนังสือ หนังสือออนไลน์ อ่านหนังสือออนไลน์ ดาวน์โหลดหนังสือฟรี อ่านหนังสือ อ่านหนังสือออนไลน์ อ่าน ห้องสมุดออนไลน์ หนังสืออ่าน อ่านหนังสือออนไลน์ฟรี อ่านหนังสือฟรี ebook อ่านหนังสือออนไลน์ หนังสือคณิตศาสตร์ที่ดีที่สุด และฟิสิกส์, หนังสือคณิตศาสตร์และฟิสิกส์ที่น่าสนใจ, e-book, หนังสือฟรี, หนังสือดาวน์โหลดฟรี, ดาวน์โหลดหนังสือคณิตศาสตร์และฟิสิกส์ฟรี, ดาวน์โหลดหนังสือฟรีแบบสมบูรณ์, ห้องสมุดออนไลน์, ดาวน์โหลดหนังสือฟรี, อ่านหนังสือออนไลน์ฟรีไม่ต้องลงทะเบียน คณิตศาสตร์และฟิสิกส์, อ่านหนังสือออนไลน์ฟรีคณิตศาสตร์และฟิสิกส์, ห้องสมุดอิเล็กทรอนิกส์คณิตศาสตร์และฟิสิกส์, หนังสืออ่านคณิตศาสตร์และฟิสิกส์ออนไลน์, โลกของหนังสือคณิตศาสตร์และฟิสิกส์, อ่านคณิตศาสตร์และฟิสิกส์ฟรี, ห้องสมุดคณิตศาสตร์และฟิสิกส์ออนไลน์, อ่านหนังสือ คณิตศาสตร์และฟิสิกส์ หนังสือคณิตศาสตร์และฟิสิกส์ออนไลน์ฟรี หนังสือคณิตศาสตร์และฟิสิกส์ยอดนิยม ห้องสมุดหนังสือคณิตศาสตร์และฟิสิกส์ฟรี ดาวน์โหลด electr หนังสือคณิตศาสตร์และฟิสิกส์ฟรี, ห้องสมุดคณิตศาสตร์และฟิสิกส์ออนไลน์ฟรี, ดาวน์โหลดหนังสืออิเล็กทรอนิกส์, หนังสือเรียนคณิตศาสตร์และฟิสิกส์ออนไลน์, ห้องสมุดอิเล็กทรอนิกส์คณิตศาสตร์และฟิสิกส์, ดาวน์โหลด e-books ฟรีโดยไม่ต้องลงทะเบียน คณิตศาสตร์และฟิสิกส์ หนังสือคณิตศาสตร์และฟิสิกส์ที่ดี ดาวน์โหลด หนังสือคณิตศาสตร์และฟิสิกส์เต็มรูปแบบ, ห้องสมุดอิเล็กทรอนิกส์อ่านคณิตศาสตร์และฟิสิกส์ฟรี, ห้องสมุดอิเล็กทรอนิกส์ดาวน์โหลดฟรีคณิตศาสตร์และฟิสิกส์, ไซต์สำหรับดาวน์โหลดหนังสือคณิตศาสตร์และฟิสิกส์, หนังสือคณิตศาสตร์และฟิสิกส์อัจฉริยะ, ค้นหาหนังสือคณิตศาสตร์และฟิสิกส์, ดาวน์โหลด e-books คณิตศาสตร์ฟรี และฟิสิกส์ ดาวน์โหลด e-book คณิตศาสตร์และฟิสิกส์ หนังสือที่ดีที่สุดเกี่ยวกับคณิตศาสตร์และฟิสิกส์ ห้องสมุดอิเล็กทรอนิกส์สำหรับคณิตศาสตร์และฟิสิกส์ฟรี อ่านหนังสือออนไลน์ฟรีเกี่ยวกับคณิตศาสตร์และฟิสิกส์ เว็บไซต์สำหรับหนังสือเกี่ยวกับคณิตศาสตร์และฟิสิกส์ ห้องสมุดอิเล็กทรอนิกส์ หนังสือออนไลน์ อ่าน, หนังสือคณิตศาสตร์อิเล็กทรอนิกส์และฟิสิกส์, เว็บไซต์ดาวน์โหลดหนังสือฟรีและไม่ต้องลงทะเบียน ห้องสมุดออนไลน์ฟรีของคณิตศาสตร์และฟิสิกส์ ซึ่งคุณสามารถดาวน์โหลดหนังสือคณิตศาสตร์และฟิสิกส์ได้ฟรี อ่านหนังสือฟรีและไม่ต้องลงทะเบียนคณิตศาสตร์และฟิสิกส์ ดาวน์โหลดตำราคณิตศาสตร์และฟิสิกส์ ดาวน์โหลด e-book ของคณิตศาสตร์และฟิสิกส์ฟรี ดาวน์โหลดหนังสือฟรีอย่างสมบูรณ์, ห้องสมุดออนไลน์ฟรี, e-books คณิตศาสตร์และฟิสิกส์ที่ดีที่สุด, ห้องสมุดออนไลน์ของหนังสือคณิตศาสตร์และฟิสิกส์, ดาวน์โหลด e-books ฟรีโดยไม่ต้องลงทะเบียน, ดาวน์โหลดห้องสมุดออนไลน์ฟรี, สถานที่ดาวน์โหลดหนังสือฟรี, e- ห้องสมุดฟรี, หนังสืออิเล็กทรอนิกส์ฟรี, ห้องสมุดอิเล็กทรอนิกส์ฟรี, ห้องสมุดออนไลน์ฟรี, อ่านหนังสือฟรี, หนังสือออนไลน์อ่านฟรี, อ่านออนไลน์ฟรี, หนังสือน่าอ่านคณิตศาสตร์และฟิสิกส์ออนไลน์, อ่านหนังสือคณิตศาสตร์ออนไลน์และ ฟิสิกส์, ห้องสมุดอิเล็กทรอนิกส์ออนไลน์คณิตศาสตร์และฟิสิกส์, ห้องสมุดหนังสืออิเล็กทรอนิกส์คณิตศาสตร์และฟิสิกส์ฟรี, ห้องสมุดออนไลน์สำหรับอ่าน, อ่านฟรีและไม่ต้องลงทะเบียน และคณิตศาสตร์และฟิสิกส์, หาหนังสือคณิตศาสตร์และฟิสิกส์, แคตตาล็อกหนังสือคณิตศาสตร์และฟิสิกส์, ดาวน์โหลดหนังสือออนไลน์สำหรับคณิตศาสตร์และฟิสิกส์ฟรี, ห้องสมุดออนไลน์ของคณิตศาสตร์และฟิสิกส์, ดาวน์โหลดหนังสือฟรีโดยไม่ต้องลงทะเบียนคณิตศาสตร์และฟิสิกส์ซึ่งคุณสามารถดาวน์โหลดได้ หนังสือคณิตศาสตร์และฟิสิกส์ฟรี ที่ซึ่งคุณสามารถดาวน์โหลดหนังสือ ไซต์สำหรับดาวน์โหลดหนังสือฟรี ออนไลน์เพื่ออ่าน ห้องสมุดเพื่ออ่าน หนังสืออ่านออนไลน์ฟรีโดยไม่ต้องลงทะเบียน ห้องสมุดหนังสือ ห้องสมุดออนไลน์ฟรี ห้องสมุดออนไลน์ให้อ่านฟรี , หนังสืออ่านฟรีและไม่ต้องลงทะเบียน, ห้องสมุดอิเล็กทรอนิกส์ให้ดาวน์โหลดหนังสือฟรี, อ่านออนไลน์ฟรี

,
ตั้งแต่ปี 2017 เป็นต้นไป เรากลับมาใช้เว็บไซต์เวอร์ชันมือถือสำหรับโทรศัพท์มือถืออีกครั้ง (การออกแบบข้อความแบบย่อ เทคโนโลยี WAP) ซึ่งเป็นปุ่มบนสุดที่มุมซ้ายบนของหน้าเว็บ หากคุณไม่มีการเข้าถึงอินเทอร์เน็ตผ่านคอมพิวเตอร์ส่วนบุคคลหรือจุดเชื่อมต่ออินเทอร์เน็ต คุณสามารถใช้โทรศัพท์มือถือของคุณเพื่อเยี่ยมชมเว็บไซต์ของเรา (แบบย่อ) และหากจำเป็น ให้บันทึกข้อมูลจากเว็บไซต์ลงในหน่วยความจำโทรศัพท์มือถือของคุณ บันทึกหนังสือและบทความลงในโทรศัพท์มือถือของคุณ (อินเทอร์เน็ตบนมือถือ) และดาวน์โหลดจากโทรศัพท์ของคุณไปยังคอมพิวเตอร์ของคุณ ดาวน์โหลดหนังสือผ่านโทรศัพท์มือถือ (ไปยังหน่วยความจำโทรศัพท์) และคอมพิวเตอร์ผ่านอินเทอร์เฟซมือถือได้อย่างสะดวก อินเทอร์เน็ตเร็วโดยไม่ต้องใช้แท็กที่ไม่จำเป็น ฟรี (สำหรับค่าบริการอินเทอร์เน็ต) และไม่มีรหัสผ่าน มีการจัดหาวัสดุสำหรับการตรวจสอบ ห้ามเชื่อมโยงโดยตรงไปยังไฟล์หนังสือและบทความบนเว็บไซต์และการขายโดยบุคคลที่สาม

บันทึก. ลิงก์ข้อความที่สะดวกสำหรับฟอรัม บล็อก การอ้างอิงเนื้อหาเว็บไซต์ สามารถคัดลอกและวางโค้ด html ลงในหน้าเว็บของคุณเมื่ออ้างอิงเนื้อหาเว็บไซต์ของเรา มีการจัดหาวัสดุสำหรับการตรวจสอบ บันทึกหนังสือลงในโทรศัพท์มือถือของคุณผ่านทางอินเทอร์เน็ต (มีไซต์เวอร์ชันสำหรับมือถือ - ลิงก์อยู่ที่ด้านบนซ้ายของหน้า) และดาวน์โหลดหนังสือจากโทรศัพท์ของคุณไปยังคอมพิวเตอร์ ห้ามลิงก์โดยตรงไปยังไฟล์หนังสือ

เป็นครั้งแรกในภาษารัสเซีย หนังสือเล่มนี้ได้นำเสนอการนำเสนออย่างเป็นระบบเกี่ยวกับพื้นฐานทางวิทยาศาสตร์ของการเข้ารหัสตั้งแต่ตัวอย่างที่ง่ายที่สุดและแนวคิดพื้นฐานไปจนถึงการสร้างการเข้ารหัสที่ทันสมัย การทำความเข้าใจหลักการของการเข้ารหัสกลายเป็นสิ่งจำเป็นสำหรับหลาย ๆ คนเนื่องจากการใช้เครื่องมือรักษาความปลอดภัยข้อมูลการเข้ารหัสอย่างแพร่หลาย ดังนั้นหนังสือเล่มนี้จึงมีประโยชน์ต่อผู้อ่านทั่วไป
หนังสือเล่มนี้มีไว้สำหรับนักเรียนของคณิตศาสตร์และผู้เชี่ยวชาญด้านความปลอดภัยของข้อมูล

เรื่องของการเข้ารหัส
หัวข้อของการเข้ารหัสคืออะไร? เพื่อตอบคำถามนี้ ให้เรากลับไปที่ปัญหา TP เพื่อชี้แจงสถานการณ์และแนวคิดที่ใช้

ก่อนอื่น เราทราบว่าปัญหานี้เกิดขึ้นเฉพาะกับข้อมูลที่ต้องการการป้องกันเท่านั้น โดยปกติในกรณีดังกล่าว จะมีการกล่าวว่าข้อมูลมีความลับหรือได้รับการคุ้มครอง เป็นส่วนตัว เป็นความลับ เป็นความลับ สำหรับสถานการณ์ทั่วไปที่พบได้บ่อยในประเภทนี้ แม้แต่แนวคิดพิเศษก็ได้รับการแนะนำ:
- ความลับของรัฐ
- ความลับทางการทหาร
- ความลับทางการค้า;
- ความลับทางกฎหมาย
- ความลับทางการแพทย์ ฯลฯ

นอกจากนี้ เราจะพูดถึงข้อมูลที่ได้รับการคุ้มครอง โดยคำนึงถึงคุณลักษณะต่อไปนี้ของข้อมูลดังกล่าว:
- มีผู้ใช้ที่ถูกต้องตามกฎหมายบางกลุ่มที่มีสิทธิ์เป็นเจ้าของข้อมูลนี้
- มีผู้ใช้ที่ผิดกฎหมายที่ต้องการรับข้อมูลนี้เพื่อ เพื่อเปลี่ยนเป็นผลประโยชน์ของตนเองและเพื่อความเสียหายต่อผู้ใช้ที่ถูกต้องตามกฎหมาย

เพื่อความง่าย อันดับแรก เราจะจำกัดตัวเองให้พิจารณาภัยคุกคามเดียวเท่านั้น - ภัยคุกคามจากการเปิดเผยข้อมูล มีภัยคุกคามอื่น ๆ ต่อข้อมูลที่ได้รับการคุ้มครองจากผู้ใช้ที่ผิดกฎหมาย: การแทนที่ การเลียนแบบ ฯลฯ เราจะพูดถึงพวกเขาด้านล่าง

สารบัญ
คำนำ
บทที่ 1 แนวคิดพื้นฐานของการเข้ารหัส
§หนึ่ง. บทนำ
§2. เรื่องของการเข้ารหัส
§3. พื้นฐานทางคณิตศาสตร์
§สี่. จุดหมายปลายทางใหม่
§5. บทสรุป
บทที่ 2 ทฤษฎีการเข้ารหัสและความซับซ้อน
§หนึ่ง. บทนำ
§2. การเข้ารหัสและสมมติฐาน P = NP
§3. ฟังก์ชันทางเดียว
§สี่. เครื่องกำเนิดสุ่มเทียม
§5. หลักฐานความรู้ที่เป็นศูนย์
บทที่ 3 โปรโตคอลการเข้ารหัส
§หนึ่ง. บทนำ
§2. ความซื่อสัตย์. โปรโตคอลการตรวจสอบสิทธิ์และลายเซ็นอิเล็กทรอนิกส์
§3. ไม่สามารถติดตามได้ เงินอิเล็กทรอนิกส์
§สี่. โปรโตคอลการโยนเหรียญ
§5. เพิ่มเติมเกี่ยวกับการแบ่งปันความลับ
§6. มาเล่นลูกเต๋ากันเถอะ ระเบียบการลงคะแนนเสียง
§7. เหนือกว่าสมมติฐานมาตรฐาน ข้อความลับ
§แปด. แทนที่จะได้ข้อสรุป
บทที่ 4
§หนึ่ง. บทนำ
§2. ระบบเข้ารหัส RSA
§3. ความซับซ้อนของอัลกอริธึมเชิงตัวเลข
§สี่. วิธีบอกจำนวนประกอบจากจำนวนเฉพาะ
§5. วิธีสร้างไพรม์ขนาดใหญ่
§6. วิธีตรวจสอบว่าจำนวนที่มากเป็นจำนวนเฉพาะหรือไม่
§7. วิธีแยกตัวประกอบตัวเลขประกอบ
§แปด. ลอการิทึมแบบไม่ต่อเนื่อง
§9. บทสรุป
บทที่ 5 คณิตศาสตร์ของการแบ่งปันความลับ
§หนึ่ง. บทนำ
§2. การแบ่งปันความลับสำหรับโครงสร้างการเข้าถึงโดยพลการ
§3. การแบ่งปันความลับเชิงเส้น
§สี่. การแยกความลับและมาทรอยด์ที่สมบูรณ์แบบ
บทที่ 6
§หนึ่ง. แทนการแนะนำตัว
§2. ทฤษฎีเล็กน้อย
§3. วิธีการเข้ารหัสไฟล์?
§สี่. มาเรียนรู้จากความผิดพลาดของผู้อื่น
§5. แทนที่จะได้ข้อสรุป
บทที่ 7
§หนึ่ง. บทนำ
§2. รหัสทดแทน
§3. รหัสการเรียงสับเปลี่ยน
§สี่. รหัสการแทนที่แบบโพลีอัลฟาเบติกด้วยคีย์เป็นระยะ
§5. เงื่อนไขปัญหาของการแข่งขันกีฬาโอลิมปิกในวิชาคณิตศาสตร์และการเข้ารหัส
§6. ทิศทางและแนวทางแก้ไข
ภาคผนวก A. ข้อความที่ตัดตอนมาจากบทความโดย K. Shannon "ทฤษฎีการสื่อสารในระบบลับ"
ภาคผนวก ข. รายการแนะนำการอ่านที่มีคำอธิบายประกอบ
ภาคผนวก B. อภิธานศัพท์ของคำศัพท์การเข้ารหัส
ดัชนีตามตัวอักษรของศัพท์ภาษารัสเซีย
ดัชนีตามตัวอักษรของคำศัพท์ภาษาอังกฤษ

ดาวน์โหลดฟรี e-book ในรูปแบบที่สะดวก ดูและอ่าน:
ดาวน์โหลดหนังสือ Introduction to cryptography, Yaschenko V.V., 2012 - fileskachat.com ดาวน์โหลดได้อย่างรวดเร็วและฟรี

ดาวน์โหลด pdf
ด้านล่างนี้คุณสามารถซื้อหนังสือเล่มนี้ได้ในราคาลดดีที่สุดพร้อมจัดส่งทั่วรัสเซีย

ในวิทยาการเข้ารหัสลับ จำนวนเฉพาะแบบสุ่มจะเข้าใจว่าเป็นจำนวนเฉพาะที่มีจำนวนบิตที่กำหนดในสัญกรณ์ไบนารี บนอัลกอริธึมการสร้างซึ่งมีการกำหนดข้อจำกัดบางประการ การรับจำนวนเฉพาะแบบสุ่มคือ ... ... Wikipedia

มาร์ติน เฮลแมน มาร์ติน เฮลแมน (Martin E. Hellman; เกิด 2 ตุลาคม ค.ศ. 1945) เป็นนักเขียนโค้ดชาวอเมริกัน ได้รับชื่อเสียงจากการพัฒนาระบบเข้ารหัสลับแบบอสมมาตรระบบแรกโดยร่วมมือกับ Whitfield Diffie และ Ralph Merkle (1976) หนึ่งใน ... ... Wikipedia

เครื่องเข้ารหัส Lorenz ของเยอรมันถูกใช้ในช่วงสงครามโลกครั้งที่สองเพื่อเข้ารหัสข้อความที่เป็นความลับที่สุด การเข้ารหัสลับ (จากภาษากรีกอื่น ๆ ... Wikipedia

เครื่องเข้ารหัส Lorenz ของเยอรมันถูกใช้ในช่วงสงครามโลกครั้งที่สองเพื่อเข้ารหัสข้อความที่เป็นความลับที่สุด การเข้ารหัส (จากภาษากรีก κρυπτός ที่ซ่อนอยู่ และ γράφω ฉันเขียน) ศาสตร์แห่งวิธีการทางคณิตศาสตร์สำหรับการรักษาความลับ ... ... Wikipedia

การแยกตัวประกอบของจำนวนธรรมชาติคือการสลายตัวเป็นผลคูณของตัวประกอบเฉพาะ การมีอยู่และความเป็นเอกลักษณ์ (ขึ้นอยู่กับลำดับของปัจจัย) ของการสลายตัวดังกล่าวตามมาจากทฤษฎีบทพื้นฐานของเลขคณิต ไม่เหมือน ... ... Wikipedia

ประกอบด้วยขั้นตอนที่ให้: การรวมผู้ใช้ในระบบ การสร้าง การแจกจ่าย และการแนะนำกุญแจสู่อุปกรณ์ การควบคุมการใช้คีย์ การเปลี่ยนแปลงและการทำลายกุญแจ การเก็บถาวร จัดเก็บ และกู้คืนคีย์ ... ... Wikipedia

บทความนี้จำเป็นต้องเขียนใหม่ทั้งหมด อาจมีคำอธิบายในหน้าพูดคุย ระบบการสื่อสารมีสองประเภท: ดิจิตอลและอนาล็อก ... Wikipedia

จำนวนเฉพาะคือจำนวนธรรมชาติที่มีตัวหารธรรมชาติต่างกันสองตัว: ตัวหนึ่งกับตัวมันเอง จำนวนธรรมชาติอื่น ๆ ทั้งหมด ยกเว้นหนึ่ง เรียกว่าประกอบ ดังนั้นจำนวนธรรมชาติทั้งหมดจึงมากกว่า 1 ... ... Wikipedia

การทดสอบพหุนามพหุนามความน่าจะเป็น การทดสอบ Miller Rabin ช่วยให้คุณระบุได้อย่างมีประสิทธิภาพว่าตัวเลขที่ระบุนั้นเป็นจำนวนรวมหรือไม่ อย่างไรก็ตาม ไม่สามารถใช้เพื่อพิสูจน์อย่างจริงจังว่าจำนวนนั้นเป็นจำนวนเฉพาะ อย่างไรก็ตามการทดสอบ Miller Rabin มักจะ ... ... Wikipedia

การทดสอบไพรมาลิตี้เป็นอัลกอริธึมที่กำหนดจำนวนธรรมชาติซึ่งกำหนดว่าจำนวนที่กำหนดนั้นเป็นจำนวนเฉพาะหรือไม่ มีการทดสอบเชิงกำหนดและความน่าจะเป็น การพิจารณาความง่ายของตัวเลขที่ระบุในกรณีทั่วไปนั้นไม่ใช่เรื่องง่าย เท่านั้น ... ... Wikipedia

โหมดการเข้ารหัส วิธีการใช้รหัสบล็อกเพื่อแปลงลำดับของบล็อกข้อมูลธรรมดาเป็นลำดับของบล็อกข้อมูลที่เข้ารหัส ในเวลาเดียวกัน ข้อมูลจากที่อื่นสามารถใช้เข้ารหัสบล็อกหนึ่งได้ ... Wikipedia