เริ่มต้นใช้งานระบบเข้ารหัส SRVB

บทนำ

ความปลอดภัยของข้อมูลเป็นสาขาความรู้ที่น่าสนใจซึ่งสามารถเกี่ยวข้องกับอะไรก็ได้ตั้งแต่วิทยาการคอมพิวเตอร์เชิงทฤษฎีไปจนถึงวิศวกรรมซอฟต์แวร์ และแม้แต่การสังเกตจิตวิทยาของความผิดพลาดของมนุษย์

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

บทความนี้จะแนะนำหลักการเบื้องหลังระบบเข้ารหัสคีย์สาธารณะ และแนะนำคุณให้รู้จักกับ Santana Rocha-Villas Boas (SRVB) ซึ่งเป็นระบบเข้ารหัสที่พัฒนาโดยผู้เขียนบทความและ Prof. Daniel Santana Rocha ในขณะที่เขียน ผู้เขียนอัลกอริทึมกำลังจัดทำแคมเปญที่มีรางวัลทางการเงินให้กับใครก็ตามที่สามารถถอดรหัสรหัสได้ เนื่องจากบทความนี้จะกล่าวถึงรายละเอียดการทำงานของอัลกอริทึม จึงเป็นจุดเริ่มต้นที่ดีที่สุดในการแสวงหารางวัล ข้อมูลเพิ่มเติมมีอยู่ในเว็บไซต์ SRVB

Cryptosystem คืออะไร?

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

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

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

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

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

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

ระบบเข้ารหัสคีย์สาธารณะ

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

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

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

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

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

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

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

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

ตัวอย่างที่ใช้จริงในระบบเข้ารหัส RSA คือการคูณจำนวนเฉพาะขนาดใหญ่กับการแยกตัวประกอบผลิตภัณฑ์ที่ได้ผลลัพธ์โดยไม่ทราบปัจจัยอยู่แล้ว การคูณเป็นเรื่องเล็กน้อย แต่การแฟคตอริ่งต้องการให้คุณสุ่ม ^[2] เดาปัจจัยเฉพาะซึ่งมีตัวเลขหลายร้อยหลัก คุณสมบัติที่สำคัญของการดำเนินการคือความจำเป็นในการขยายขนาดให้ดี การเพิ่มตัวเลขสองสามหลักบนขนาดของจำนวนเฉพาะใน RSA จะส่งผลให้คีย์ต้องมีการดำเนินการมากกว่าพันครั้งในการถอดรหัส ขณะที่เพิ่มความซับซ้อนเพิ่มขึ้นเล็กน้อยในกระบวนการเข้ารหัส กล่าวโดยคร่าว ๆ ผลคูณของจำนวนเฉพาะใช้สำหรับการเข้ารหัส ในขณะที่ปัจจัยเฉพาะคู่จะใช้สำหรับการถอดรหัส

เมื่อคำนึงถึงทั้งหมดนี้ มาดูกันว่าระบบการเข้ารหัส SRVB ทำงานอย่างไร

อัลกอริทึมพื้นฐาน - พิจารณา SRVB

ปัญหาผลรวมย่อย

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

จากจำนวนเต็ม $w$ และ $v_1 \cdot \cdot \cdot, v_N \in Z$ ค้นหาลำดับ $b_1, \cdot \cdot \cdot, b_N \in {0,1}$ เช่นนั้น $ \sum_ {i = 1}^{N} v_i b_i = w $.

เห็นได้ชัดว่าปัญหานี้เกิดขึ้นได้จากการสุ่มเลือกจำนวนเต็ม N สุ่มเลือกชุดย่อยและสรุปชุดย่อยนี้ ซึ่งถือว่าไม่สำคัญ

การค้นหาแบบเดรัจฉานจะมีความซับซ้อน $ O( N * 2^N ) $ โดยคำนวณหาค่าผสมของ $b$s แต่ละค่า Horowitz และ Sahni ให้แนวทางที่มีประสิทธิภาพมากขึ้นในปี 1972 โดยมีความซับซ้อน $ O ( N * 2 ^ {N / 2} ) $ ปัญหาอย่างน้อยก็ยากถ้าเราแทนที่ $b$s และ $w$ ด้วยเวกเตอร์มิติของ $k$- ของจำนวนเต็ม อย่างไรก็ตาม ขอบเขตที่จะจัดการกับปัญหาที่ยากกว่านี้ จะต้องมี isomorphism กับวงแหวนซึ่งปัญหาเดียวกันจะเกิดขึ้นในรูปแบบที่ง่ายกว่า ดังที่เราจะเห็นด้านล่าง ด้วยเหตุผลนี้ SRVB ใช้ประโยชน์จากปัญหาผลรวมของเซตย่อยภายในจำนวนเต็มเกาส์เซียน โดยที่ $ k = 2 $

มีกรณีพิเศษที่ปัญหานี้สามารถคำนวณได้ง่ายโดยใช้อัลกอริธึมที่โลภ หากเราจัดเรียงตัวประกอบการปรับขนาดลำดับ $ v_1, \cdot \cdot \cdot, v_N $ ซึ่งจำนวนเต็มแต่ละตัวในลำดับนั้นมากกว่าผลรวมของจำนวนเต็มที่มาก่อน ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $) เราสามารถใช้วิธีการโลภเพื่อค้นหาลำดับ b ในเวลาเชิงเส้น ลำดับที่มีคุณสมบัติที่อธิบายไว้เรียกว่า ลำดับที่ เพิ่มมากขึ้น

นี่คือคำอธิบายง่ายๆ เกี่ยวกับวิธีแก้ปัญหาที่โลภสำหรับกรณีนี้:

1. เริ่มต้นด้วย $ i = N $ ปัจจัยที่สังเกตได้ในปัจจุบัน และ $ w' = w $ ส่วนที่เหลือของ $w$

2. หากตัวประกอบมาตราส่วนปัจจุบันใหญ่เกินไปที่จะพอดีกับส่วนที่เหลือของ $w$ ซึ่งหมายถึง $ v_i > w'$ ให้ตั้งค่า $b_i = 0$ และดำเนินการในขั้นตอนต่อไป มิฉะนั้น เราทราบดีว่าตัวคูณมาตราส่วนต้องอยู่ในลำดับ (เนื่องจากปัจจัยที่เหลือน้อยกว่า $v_i$) และเราตั้งค่า $b_i = 1$

3. $ w' \leftarrow w' - v_i * b_i$, $i \Leftarrow i - 1$. ถ้า $i > 0$ ให้กลับไปที่ขั้นตอนที่ 2

4. ตรวจสอบว่าตอนนี้ $w' == 0$ มิฉะนั้น ปัญหาได้รับความเสียหาย

สิ่งนี้ใช้ได้เพราะเรารู้ว่าตัวคูณทั้งหมดที่เล็กกว่าตัวคูณที่สังเกตได้ในปัจจุบันไม่สามารถรวม (ย่อย)ผลรวม $ w' $ ได้มากเท่าที่ตัวคูณปัจจุบันสามารถทำได้ ดังนั้นหากผลรวมที่เหลือมากกว่าปัจจัยปัจจุบัน เราทราบแน่ชัดว่าปัจจัยที่ตามมาทั้งหมดจะไม่สามารถสรุปรวมได้หากไม่ได้รับความช่วยเหลือจากปัจจัยปัจจุบัน ในทางกลับกัน เนื่องจากตัวคูณทั้งหมดเป็นค่าบวก หากตัวประกอบปัจจุบัน $ v_i $ มากกว่าผลรวม $ w' $ ที่เหลือ การเพิ่มปัจจัยอื่นจะทำให้ผลลัพธ์เกิน $ w' $ มากยิ่งขึ้น

มาตั้งค่าสัญกรณ์สำหรับบทความที่เหลือกัน เราเลือก $ v_1, \cdot \cdot \cdot, v_n $ และ $w$ เป็นตัวประกอบและผลรวมของลำดับการเพิ่มยิ่งยวด ในขณะที่ $ u_1, \cdot \cdot \cdot, u_n $ และ $y$ จะเปิดเผยต่อสาธารณะ พารามิเตอร์ที่มีให้เพื่อกู้คืน $ b_1, \cdot \cdot \cdot, b_n $

ด้วยลำดับ $ u_1, \cdot \cdot \cdot, u_n $ ถูกเลือกดังนั้นจึงไม่เพิ่มขึ้นอย่างมาก และหมายเลข $y$ ถูกเปิดเผยต่อสาธารณะ ข้อมูลที่เปิดเผยต่อสาธารณะไม่เพียงพอสำหรับการกู้คืนลำดับ $ b_1, \cdot \cdot \cdot , b_n $. อย่างไรก็ตาม หากมีลำดับที่เพิ่มมากขึ้น $ v_1, \cdot \cdot \cdot, v_n $ ที่อาจแทนที่ลำดับ $ u_1, \cdot \cdot \cdot, u_n $ เราสามารถใช้ลำดับนี้เพื่อแก้ปัญหาด้วย วิธีการโลภ

ด้านล่างเราจะแสดงวิธีการทำงาน

การใช้ Subset Sums ใน Cryptosystem ก่อนหน้า

ในปีพ.ศ. 2521 Ralph Merkle และ Martin Helman ได้คิดค้นวิธีใช้ประโยชน์จากกระบวนทัศน์ของเป้สะพายหลังทั้งสองแบบและความเป็นเส้นตรงของการดำเนินการโมดูลัสเพื่อสร้างการเชื่อมต่อระหว่างสองลำดับที่อธิบายไว้ในส่วนก่อนหน้า ดังนั้นจึงทำให้เกิดระบบเข้ารหัสกุญแจสาธารณะ แนวคิดคือการแปลง เป้แบบง่าย (อันที่ประกอบด้วยเวกเตอร์การเพิ่มขึ้นยิ่งยวดของจำนวนเต็ม) ให้เป็นแบบแข็ง (อันที่ไม่มีคุณสมบัตินี้) โดยใช้การดำเนินการเชิงเส้น (โมดูลัส) กับตัวถูกดำเนินการลับ การแปลงประกอบด้วยการคูณทุก ๆ $v_i$ ด้วย $\theta$ และนำเศษที่เหลือของผลิตภัณฑ์นี้ไปคูณกับ $\alpha$ โดยที่ $\alpha \gt \sum_{i=1}^N v_i$ และ $\gcd (\alpha, \theta) = 1$ (ข้อจำกัดสองข้อที่จะได้รับการพิสูจน์ในไม่ช้า) ผลลัพธ์ ลำดับ $u_1, \ldots, u_N$, ไม่ได้เพิ่มขึ้นอย่างมากอีกต่อไป และถือได้ว่าเป็น เป้แบบแข็ง

การเรียงสับเปลี่ยนแบบสุ่มของลำดับ $u_1, \ldots, u_N$ จะมอบให้กับบุคคลที่ต้องการเข้ารหัสและส่งข้อความถึงเรา การเปลี่ยนแปลงนี้ทำขึ้นเพื่อให้บุคคลที่สามมีเวลามากขึ้นในการคาดเดาว่าลำดับการเพิ่มยิ่งยวดดั้งเดิมคืออะไร บิตบล็อกของข้อความถูกใช้เป็นสัมประสิทธิ์ $b_1, \ldots, b_N$ การเข้ารหัสทำได้โดยการคูณลำดับคีย์ด้วยลำดับสัมประสิทธิ์นี้ และรวมการคูณเข้าด้วยกันเป็นผลลัพธ์ เราจะติดป้ายกำกับ $y$ เฉพาะเจ้าของคีย์ส่วนตัวเท่านั้นที่สามารถแปลง $y$ เป็น $w$ ที่สอดคล้องกันซึ่งจะได้รับหาก $b_1, \ldots, b_N$ บล็อกเดียวกันนี้จะถูกคูณด้วย จำนวนเต็มง่าย (ลำดับ $v_1, \ldots , v_N$) ทำได้โดยการคูณ $y$ ด้วย $\theta^{-1}$ ตัวผกผันการคูณของ $\theta$ โมดูลัส $\alpha$ (ซึ่งการดำรงอยู่ขึ้นอยู่กับเงื่อนไขนั้นของ $\gcd(\alpha, \ ที) = 1$) กล่าวอีกนัยหนึ่ง $(\theta * \theta^{-1}) \bmod \alpha = 1$ หลังจากนั้น เราจะคำนวณ $w = (y * \theta^{-1}) \bmod a$ เหตุผลที่รับประกันว่าจะได้ผลก็คือความเป็น เชิงเส้นของโมดูลัส กล่าวคือ ผลรวมเชิงเส้นของเศษที่เหลือจะเท่ากับส่วนที่เหลือของผลรวมเชิงเส้น

หากเราใช้คำจำกัดความของ $u$ วงแหวนผลหาร และคุณสมบัติของความเป็นเส้นตรงของตัวดำเนินการโมดูลัสอย่างต่อเนื่อง เราจะเห็นความสอดคล้องกัน:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ ซ้าย[ \sum_{i=1}^N b_i * v_i \right] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

ดังนั้น ผลรวมอย่างง่าย $w$ สามารถกู้คืนได้โดยการคูณทั้งสองข้างด้วย $\theta^{-1}$ และรับโมดูลัสด้วย $\alpha$ ในการทำเช่นนั้น เราต้องรู้ทั้ง $\alpha$ และ $\theta$ (ซึ่งอนุญาตให้คำนวณ $\theta^{-1}$ อย่างง่ายดาย) ซึ่งจะถูกเก็บไว้เป็นส่วนตัวโดยเป็นส่วนหนึ่งของคีย์ส่วนตัว

ข้อจำกัดเดียว $\alpha \gt \sum_{i=1}^N v_i$ ถูกปล่อยให้ไม่ยุติธรรม และนี่คือคำอธิบาย: ความเท่าเทียมกันระหว่างบรรทัดที่สองและสามประกอบด้วยความเท่าเทียมกันระหว่างคลาสที่เหลือของผลหาร วงแหวนของจำนวนเต็ม โมดูโล $\alpha$ กล่าวอีกนัยหนึ่งคือระบุความเท่าเทียมกันของส่วนที่เหลือของสมาชิกเมื่อหารด้วย $\alpha$ ซึ่งเป็นเงื่อนไขที่ไม่เพียงพอสำหรับความเท่าเทียมกันของสมาชิกเอง เป็นผลให้สามารถจับคู่เวกเตอร์ของค่า $b$ มากกว่าหนึ่งค่าใน $y$ เดียว ซึ่งป้องกันได้โดยการจำกัดผลรวมย่อยสูงสุดที่เป็นไปได้ (เช่น ผลรวมของพัสดุทั้งหมด $v_i$) $w_{max}$ ถึง มีค่าน้อยกว่า $\alpha$ สำหรับค่า $b$ ผสมกัน

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

The Santana Rocha - Villas Boas (SRVB) Cryptosystem

ในปี 2016 หลังจากระดมความคิดกับผู้เขียนบทความนี้ไม่กี่ครั้งเกี่ยวกับความเป็นไปได้ ^[3] ของระบบเข้ารหัสลับที่ต่างกันออกไป Daniel Santana Rocha มีแนวคิดที่จะแทนที่ $\theta$ และ $\alpha$ โดย Gaussian Integers ด้วยเหตุผลทางเทคนิคเพิ่มเติม แนวทางนี้นำไปสู่การต่อต้านการโจมตีของ Shamir ดังกล่าว

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

$\alpha$ ซึ่งปัจจุบันเป็นจำนวนเต็มเกาส์เซียนจะใช้ข้อจำกัดที่แตกต่างกันแต่มีความคล้ายคลึงกันอย่างหรูหรา เราต้องการ $w_{max} \leq \vert\alpha\vert^2$ เหตุผลนั้นยากมากที่จะทำให้เป็นทางการ แต่โชคดีที่เข้าใจได้ง่ายจากคำอธิบายที่หรูหรา:

ลองนึกภาพตาข่ายสี่เหลี่ยมจัตุรัสในระนาบของจำนวนเชิงซ้อนซึ่งมีด้านตรงข้ามมุมฉากของสามเหลี่ยมมุมฉากของ catheti a และ b ขนานกับแกนจริงและแกนจินตภาพ ตัวอย่างของตาข่ายดังกล่าวแสดงไว้ด้านล่าง จำนวนเต็ม Guassian modulo $\alpha = a + bi$ สามารถแทนด้วยจุดที่อยู่ภายในตาข่ายดังกล่าว ภายในตาข่ายดังกล่าวมีจุดที่แตกต่างกัน $\vert\alpha\vert^2$ ถ้าเราเลือก $\alpha$ ที่ใหญ่พอ เราก็สามารถใส่ชุดค่าผสมเชิงเส้นทั้งหมดของเป้ง่าย ๆ ได้

นี่คือการแสดงภาพกราฟิกของ isomorphism $f : Z/n \rightarrow Z[i]/(\alpha)$ โดยที่ $n = 13$ และ $\alpha = a + bi = 3 + 2i$ (โปรดทราบว่า $ n$ และ $\alpha$ เป็นไปตาม $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $ ตามที่ต้องการ) จุดแทนจำนวนเต็มเกาส์เซียน กล่าวคือ จำนวนเชิงซ้อน $a + bi$ โดยที่ $a$ และ $b$ เป็นจำนวนเต็ม ตามปกติ แกนนอนแสดงถึงส่วนจริง ในขณะที่แนวตั้งแสดงถึงส่วนจินตภาพ ดังนั้น การย้ายจุดไปทางขวาหรือซ้ายหนึ่งจุดจึงเท่ากับการเพิ่ม +1 หรือ -1 ให้กับค่าปัจจุบันตามลำดับ ในทำนองเดียวกัน การเลื่อนจุดขึ้นหรือลงหนึ่งจุดสอดคล้องกับการบวก +i หรือ -i ตามลำดับ

จุดสีแดงนั้นเทียบเท่ากับ $0 \bmod(\alpha)$ นอกเหนือจากนี้ เรายังระบายสีจุดอีก 4 คู่ด้วย

isomorphism $f$ ถูกกำหนดโดยการเปลี่ยนแปลงขององค์ประกอบ $i$th ของลำดับวัฏจักร $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot \cdot\cdot)$ ลงในองค์ประกอบ $i$th ของลำดับจุดแบบวนซ้ำในรูปภาพ ซึ่งเป็นไปตามกฎต่อไปนี้:

1. เริ่มจากจุดสีแดงของแถวแรก
2. มันตามลูกศรขวาแนวนอน เว้นเสียแต่ว่า
3. เมื่อเดินตามลูกศรนำไปสู่ลำดับนอกโครงตาข่าย มันจะไปถึงจุดที่ไม่ใช่จุดดำจุดใดจุดหนึ่ง แทนที่จะไปที่จุดนั้น มันจะข้ามไปยังจุดสีเดียวกัน (เช่น จุดโมดูโลที่เทียบเท่า $\alpha$) ภายในสี่เหลี่ยมเดียวกัน และในที่สุดก็
4. เมื่อจุดที่ไม่ใช่สีดำนี้เป็นสีแดง (ซึ่งเกิดขึ้นหลังจากผ่านสีอื่นๆ ทั้งหมดแล้ว) ลำดับจะข้ามไปยังจุดสีแดงบนสุด จึงเริ่มต้นวงจรใหม่

ในการแมปจำนวนเต็มธรรมชาติอย่างน้อย $Y$ เราต้องนำกำลังสองที่มีพื้นที่ $\vert\alpha\vert^2$ (โดยที่ $\vert\alpha\vert = \sqrt{a^2 + b^2} $ คือโดยทฤษฎีบทพีทาโกรัส การวัดด้านของมัน) อย่างน้อยก็สูงที่สุด

สังเกตว่า "กระโดด" แต่ละครั้งจะเปลี่ยนหมายเลขแถว $r$ เป็น $r \leftarrow (r + b)(mod a + b)$ หากนับแถวจากบนลงล่างและเทียบเท่ากับ $r \leftarrow (r + a)(mod a + b)$ ถ้านับจากล่างขึ้นบน ดังนั้น เงื่อนไขที่จำเป็นและเพียงพอสำหรับแต่ละแถว (และจุด) ที่จะโรมมิ่งเพียงครั้งเดียวในแต่ละรอบคือขนาดของการกระโดดนั้นเท่ากับ coprime กับจำนวนแถวหรือกล่าวอีกนัยหนึ่ง $gcd(a,a + b) = gcd(b,a + b) = 1$ เนื่องจากคุณสมบัติของตัวดำเนินการตัวหารร่วมมาก ทั้งสองจึงเทียบเท่ากับ $gcd(a,b) = 1$

YS Villas Boas สังเกตเห็นความจำเป็นในการเป็นคู่ของ $a$ และ $b$ เพื่อรักษาการเพิ่มขึ้นอย่างมาก จำนวนเต็มใหม่แต่ละจำนวน $w$ ที่เพิ่มที่ส่วนท้ายของลำดับจะต้องมากกว่าผลรวมของจำนวนเต็มปัจจุบันทั้งหมด ($w > \sum_{i=1}^k v_i$) เขาสังเกตว่าเพื่อให้บรรลุสิ่งนี้ สัมประสิทธิ์การคูณ $b_i$ จะต้องมีอย่างน้อย 1 ดังนั้นแต่ละบิตจึงไม่สามารถจับคู่เข้ากับสัมประสิทธิ์ 0 และ 1 หากสัมประสิทธิ์เป็น 0 และ 1 เฉพาะบล็อก ประกอบด้วยเพียงคนเดียวเท่านั้นที่จะสนองความยิ่งยวด ด้วยเหตุนี้ บิต 0 และ 1 จึงถูกแมปตามลำดับกับสัมประสิทธิ์การคูณ 1 และ 2 ตามลำดับ

สุดท้ายนี้ เป็นเรื่องเล็กน้อย: ในแต่ละขั้นตอนของการถอดรหัส จะพบจำนวนเต็ม $v_1$ ใหม่หนึ่งตัวเป็นคำตอบของสมการ $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} b_i v_i$ โดยที่ $v_i$ และ $b_i$ เป็นที่รู้จักสำหรับ $1 < i \leq n$ เนื่องจากเราไม่รู้ $b_1$ เช่นกัน เราจึงลงเอยด้วยระบบที่มีสมการเดียวและตัวแปรสองตัว ซึ่งทำให้เรามีอิสระในระดับหนึ่ง ในการแก้ไขปัญหานี้ เราต้องตัดสินค่าบวกหนึ่งค่า (เพื่อความเรียบง่าย 1) เพื่อกำหนดให้ $b_1$ เสมอ ดังนั้นจึงขจัดความกำกวมออกไป ดังนั้น เนื่องจากสัมประสิทธิ์แรกถูกกำหนดให้เป็น 1 เพื่อเข้ารหัสบิต $n$ ในแต่ละขั้นตอน ลำดับของจำนวนเต็มของเราจะต้องมีความยาวองค์ประกอบ $n + 1$

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

ตอนนี้ขอแสดงตัวอย่างของระบบการเข้ารหัส SRVB

เราเริ่มต้นด้วยพารามิเตอร์:

$k = 4$;

$m = 4$;

ซึ่งให้ความยาวบล็อกเท่ากับ $l = 4 * 4 = 16$ และลำดับการทวีคูณของ $k + 1 = 5$ จำนวนเต็มธรรมชาติที่ดำเนินการ กล่าวคือ รวมกันเชิงเส้น ต่อท้ายด้วยผลลัพธ์ของการรวมเชิงเส้นนี้ และ ลดเหลือองค์ประกอบ $k + 1$ สุดท้าย —$m = 4$ ครั้ง;

เพื่อความง่าย ให้ต่อไปนี้เป็นเวกเตอร์ (เพิ่มขึ้นมาก) ของ $v_i$:

$(1,2,4,8,16)$

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

ดังที่เราได้กล่าวไว้ก่อนหน้านี้ สำหรับ $\alpha = a + bi$ จำนวนเต็ม $a$ และ $b$ ต้องเป็น coprime และตามข้อจำกัดใหม่ที่เรากล่าวถึง เราต้องขอให้ $a^2 + b^2 = \vert\alpha\vert^2 \geq W$. การคำนวณอย่างรวดเร็วให้ผลตอบแทน $W = 1590$ ตั้งแต่ $\sqrt{1590} \simeq 39.8$ $\alpha$ ที่สะดวกมากที่จะเลือกคือ $\alpha = 39 + 40i$ เพราะมันใหญ่พอที่จะรองรับ isomorphism ด้วยวงแหวนของจำนวนเต็มโดยที่ ส่วนประกอบอย่างน้อย 1,590 รายการในขณะที่พอใจกับ $gcd(a,b)=1$ นอกจากนี้ เราต้องเลือก $\theta$ ที่ $gcd(a,\theta)=1$ ^[5] และไม่ควรต่ำเกินไป ดังนั้น $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (เพื่อหลีกเลี่ยงการให้ข้อมูลด้วย) $\theta = 60$ ทำงานโดยให้ผล:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

ให้มือเราสกปรกเสียก่อน รับข้อความ Hello Toptal! . อันดับแรก เราแมปลงในอาร์เรย์ของไบต์ตาม ASCII และแบบแผนของเราในการตัดทอนบล็อคข้อมูล:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

เนื่องจากบล็อกข้อมูลของเรามีความยาว 16 บิต = 2 ไบต์ และข้อความของเรามีอักขระ 13 ตัว เราจึงลงเอยด้วยบล็อกข้อมูล 7 บล็อก ชุดละ 2 ไบต์ โดยบล็อกสุดท้ายมีการแสดงบิตเป็นสองเท่าของอักขระ '!' . ให้เราเข้ารหัสบล็อกแรกทีละขั้นตอน ให้ความสนใจเป็นพิเศษเพราะว่าบิตของแต่ละไบต์จะถูกจัดลำดับความสำคัญ

$m=01001000 01100101$

• แทะแรกของไบต์แรก: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• แทะที่สองของไบต์แรก: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• แทะแรกของไบต์ที่สอง: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• แทะที่สองของไบต์ที่สอง: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

และด้วยเหตุนี้เราจึงเพิ่งทำแผนที่

“เขา” $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

ข้อความที่เข้ารหัสที่เหลือมีดังนี้:

“จะ” $\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

“o “ $\Rightarrow(12-12i,25+33i,65+32i,111+44i,244+124i)$

“ถึง” $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

“จุด” $\Rightarrow(12-12i,3+16i,46+12i,73+23i,201+49i)$

“อัล” $\Rightarrow(12-12i,4+54i,44+53i,117+193i,231+389i)$

“!!” $\ลูกศรขวา(12-12i,4+54i,32+65i,63+92i,121+247i)$

ตอนนี้ สำหรับการถอดรหัส เรามี $\theta^{-1}=60^{-1}=27+i$:

$($”เขา” $\ลูกศรขวา)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223,527)$

ตอนนี้อัลกอริทึมที่โลภมาถึงแล้ว:

อันดับแรก เราลบปัจจัยการคูณคูณด้วยหนึ่ง เนื่องจากเป็นที่ทราบกันดีอยู่แล้วว่ามีส่วนสนับสนุนอย่างน้อยหนึ่งครั้งในช่วงสุดท้าย โดยได้ผลลัพธ์ดังนี้

• แทะที่สองของไบต์ที่สอง:

$T \leftarrow (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = false \Rightarrow b_1=0 ; T \leftarrow (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = true \ลูกศรขวา b_3 = 1; T \leftarrow (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = false \ลูกศรขวา b_4 = 0; T \leftarrow (T - 0 * 16) = 8$

ผลลัพธ์: 0110;

ส่วนที่เหลือ: 8 (เพิ่มที่จุดเริ่มต้นของลำดับเป็นองค์ประกอบต่ำสุดใหม่);

ดรอป 527 จากลำดับสุดท้ายของลำดับปัจจุบัน

• แทะแรกของไบต์ที่สอง:

$T \leftarrow (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = false \Rightarrow b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = true \Rightarrow b_4 = 1; T \leftarrow (T - 0 * 12) = 4$

ผลลัพธ์: 0101;

ส่วนที่เหลือ: 4 (เพิ่มที่จุดเริ่มต้นของลำดับเป็นองค์ประกอบต่ำสุดใหม่);

ดรอป 233 จากลำดับสุดท้ายของลำดับปัจจุบัน

• แทะที่สองของไบต์แรก:

$T \leftarrow (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = false \ลูกศรขวา b_1 = 0; T \leftarrow (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = true \Rightarrow b_2 = 1; T \leftarrow (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = false \Rightarrow b_4 = 0; T \leftarrow (T - 0 * 4) = 2$

ผลลัพธ์: 0100;

ส่วนที่เหลือ: 2 (เพิ่มที่จุดเริ่มต้นของลำดับเป็นองค์ประกอบต่ำสุดใหม่);

ดรอป 93 จากลำดับสุดท้ายของลำดับปัจจุบัน

• แทะแรกของไบต์แรก:

$T \leftarrow (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = true \Rightarrow b_1 = 1; T \leftarrow (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = false \ลูกศรขวา b_2 = 0; T \leftarrow (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = false \Rightarrow b_3 = 0; T \leftarrow (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = false \ลูกศรขวา b_4 = 0; T \leftarrow (T - 0 * 2) = 1$

ผลลัพธ์: 1,000;

ส่วนที่เหลือ: 1 (เพิ่มที่จุดเริ่มต้นของลำดับเป็นองค์ประกอบต่ำสุดใหม่);

ดรอป 47 จากลำดับสุดท้ายของลำดับปัจจุบัน

ด้วยเหตุนี้ เราจึงกู้คืนบล็อคข้อมูล: “01001000 01100101” ที่มีอักขระสองตัวแรก “He” ของข้อความของเรา ไม่เพียงแค่นั้น เรายังดึงข้อมูลลำดับการเพิ่มคีย์ส่วนตัวของเราอย่างถูกต้อง $(1,2,4,8,16)$

แผนที่บล็อคข้อมูลอื่น ๆ ไปในลักษณะเดียวกัน

เปรียบเทียบกับระบบเข้ารหัสคีย์สาธารณะที่สำคัญ

SRVB คือ:

1. ฟรีและเป็นสาธารณะ

2. ค่อนข้างง่ายและเข้าใจและนำไปใช้ได้ง่ายกว่า ECC ^[7] ;

3. มีกุญแจมากมายและแทบไม่มีต้นทุน ตรงกันข้ามกับ RSA ซึ่งอาศัยจำนวนเฉพาะซึ่งมีราคาแพง

เราสามารถสรุปจุดอ่อนที่เป็นไปได้มากที่สุดได้แล้ว เนื่องจาก SRVB สืบเชื้อสายมาจาก MH จึงเป็นเรื่องง่ายที่จะสงสัยว่าจะมีความเสี่ยงที่จะถูกโจมตีโดย Shamir โดยรวมหรือสิ่งอื่นที่ทำลายมัน แม้ว่าผู้เขียนมีเหตุผลที่จะเชื่อว่าจะไม่เป็นเช่นนี้ แต่ก็ยังไม่มีการยืนยัน (ซึ่งเป็นเรื่องปกติมากเมื่อต้องรับมือกับ cryptosystems)

อะไรต่อไป?

Rocha สังเกตลักษณะทั่วไปสองสามประการสำหรับวงแหวนผลหารที่จะใช้ ซึ่งอาจนำไปสู่ความซับซ้อนที่เพิ่มขึ้นของการเข้ารหัสลับ เราจะตรวจสอบความเป็นไปได้เหล่านี้ด้วย

การบดบังพีชคณิตเชิงเส้น

ในระหว่างการพัฒนาและการจัดทำเอกสารของ SRVB Villas Boas ได้เสนอแนวทางอื่นในการปรับปรุงแนวคิดของระบบเข้ารหัสกุญแจสาธารณะแบบเป้ที่จะไม่ได้อธิบายในรายละเอียดมากนักในที่นี้ เพื่อไม่ให้บทความนี้ยาวเกินไป และน่าเบื่อหน่าย แต่นี่คือการดูคร่าวๆ หากคุณไม่ประสบความสำเร็จในการจับมัน ไม่ต้องกังวล เพียงคอยติดตามการเปิดตัวของบทความถัดไป ซึ่งเราจะลงรายละเอียดให้ละเอียดยิ่งขึ้น: ดูผลรวมย่อย $y$ ของ พูดว่า $N$ องค์ประกอบวงแหวนผลหาร $u_i$ (ที่สอดคล้องกับจำนวนเต็มบวก $v_i$ ของลำดับการเพิ่มขึ้นอย่างมากเหมือนเมื่อก่อน) เป็นการคูณเวกเตอร์แถวของ $u_i$ เหล่านี้ด้วยเวกเตอร์คอลัมน์ $B$ ( สำหรับเลขฐานสอง) ของศูนย์และหนึ่ง ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

โดยที่ $b_i \in {0,1}$

ทีนี้ ลองนึกภาพว่า แทนที่จะเป็นเวกเตอร์ของ $u_i$ คุณมี $n$ คูณ $N$ (ด้วย $n < N$) เมทริกซ์ V ทางซ้าย มี $v_i$ (จำนวนเต็มจากการเพิ่มขึ้นยิ่งยวด ลำดับ) เวกเตอร์เป็น (โดยไม่สูญเสียความทั่วไป) แถวแรกและรายการอื่น ๆ ทั้งหมดเต็มไปด้วยสัญญาณรบกวน สังเกตว่า ตอนนี้ การคูณ V ด้วยเวกเตอร์บิตเดียวกัน B จะทำให้คุณได้เวกเตอร์คอลัมน์ W ที่มี $w$ เป็นค่าแรกและจุดรบกวนในส่วนอื่นๆ ทีนี้ นำเมทริกซ์ V มาคูณด้วยสุ่ม ^[9] n คูณ n เมทริกซ์ R ทางด้านซ้าย กำหนด n โดย N เมทริกซ์ P:

P = RV

แนวคิดก็คือ Bob ใช้ P เป็นกุญแจสาธารณะใหม่ของเขา เนื่องจากการสุ่มของ R, เวกเตอร์

$Y = PB = RV B = RW$

มีข้อมูล $w$ บดบังโดยสัญญาณรบกวนในแถวอื่นๆ ของ V. Bob ยังคำนวณล่วงหน้าและเก็บเวกเตอร์แถว S ที่ตรงตาม:

$R^TS^T = e_1$

เมื่ออลิซส่ง Y ถึง Bob เขาเพิ่งพบ SY เพราะ:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(จนถึงคำจำกัดความเท่านั้น)

${e_1}^T (VB)={e_1}^TW = w$

(ตอนนี้ใช้ประโยชน์จากการเชื่อมโยงเพื่อยกเลิก Rs)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

รับทราบ

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

อภิธานศัพท์

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.