วิธีการใหม่ในการซ่อนข้อมูลโดยใช้จำนวนเฉพาะ?

มีการเสนอหรือศึกษาวิธีการซ่อนข้อมูลดังต่อไปนี้หรือไม่? ประสิทธิภาพหรือความปลอดภัยของวิธีนี้คืออะไร? แอปพลิเคชันใดบ้างที่สามารถใช้วิธีนี้ได้

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

$p = p_0 \ || \ ข้อมูล \ || \ p_{จบ}\ \ $ และ $ \ \ q = q_0 \ || \ เครื่องหมาย \ || \ q_{จบ}$

ที่ไหน $p_0$ และ $q_0$ เป็นแบบสุ่ม $เดี่ยว$ ตัวเลขที่ไม่ใช่ศูนย์ด้วย $p_0 < q_0$, $ข้อมูล$ เป็นตัวเลขด้วย $k$ (ทศนิยม) หลัก $เครื่องหมาย$ เป็นการสุ่มตัวเลขด้วย $k-1$ ตัวเลขที่ไม่ใช่ศูนย์ตามด้วย $0$, และ $p_{end}$ และ $q_{end}$ เป็นการสุ่มตัวเลขด้วย $n-k-1$ ตัวเลข

ข้อมูลที่เข้ารหัสคือ $N = P \คูณ Q$ ที่ไหน $พี$ และ $คิว$ เป็นจำนวนเฉพาะถัดไปหลังจาก $p$ และ $คิว$. $n$ ถูกเลือกมากพอที่จะแยกตัวประกอบของ a $2n$- ตัวเลขไม่สามารถทำได้ และเพื่อให้พร้อมกับตัวเลือกของ $p_{end}$ และ $q_{end}$,การก่อสร้าง $พี$ และ $คิว$ ไม่ก่อให้เกิด $ข้อมูล$ หรือ $เครื่องหมาย$ เพื่อเปลี่ยนแปลง.

ความคิดเห็นเล็กน้อย: (1) แม้ว่าจะมีข้อ จำกัด บางประการ $พี$ และ $คิว$ เป็นที่รู้จัก ไม่เพียงพอที่จะใช้ "การแยกตัวประกอบกับข้อมูลบางส่วน/บิตที่รู้จัก" (2) รู้ $พี$ และ $คิว$ในลำดับใด ๆ จะช่วยให้สามารถค้นหาข้อมูลที่ซ่อนอยู่โดยไม่ซ้ำกัน (3) วิธีนี้ปรับเป็นไบนารี่ได้ง่าย

ตัวอย่าง: $ข้อมูล$ คือ 271828 กับ $k$ = 6. เพื่อความเรียบง่ายในการใช้งาน $n$ = 12:

$p = \mathtt {1 \ขีดเส้นใต้ {271828} 67213}$, $P = \mathtt {1 \ขีดเส้นใต้ {271828} 67221} \ \ $ และ $ \ \ q=\mathtt {6 \ขีดเส้นใต้{97811} \ขีดเส้นใต้ {\ขีดเส้นใต้ {0}}97478}$, $Q = \mathtt {6 \ขีดเส้นใต้{97811} \ขีดเส้นใต้ {\ขีดเส้นใต้ {0}}97499}$

$N = P \times Q = \mathtt {88749616158555602180279}$.

แก้ไข: ข้อมูลสามารถเป็นจำนวนเต็มใด ๆ (ศูนย์หรือมากกว่า) เพื่อเน้นว่ามันไม่จำเป็นต้องเป็นจำนวนเฉพาะ ฉันเปลี่ยนข้อมูลตัวอย่างจาก 314159 (ซึ่งเป็นจำนวนเฉพาะ) เป็น 271828 (แบบผสม)

แก้ไข (30 มีนาคม): เพิ่ม "single" ในคำอธิบายของ $p_0$ และ $q_0$ เพื่อตอกย้ำว่าแต่ละ $p_0$ และ $q_0$ เป็นเลขหลักเดียวที่ไม่ใช่ศูนย์ โปรดทราบว่าขนาดของข้อมูล ($k$) ไม่ทราบล่วงหน้า แต่ระบุโดย $เครื่องหมาย$. นอกจากนี้ ผลลัพธ์ที่เป็นที่รู้จักกันดีที่สุดจาก Coppersmith ก็คือ การแยกตัวประกอบนั้นทำได้ง่ายหากทราบเศษส่วนครึ่งหนึ่งของตัวประกอบ

ฉันจะตรวจสอบว่านี่เป็นแผนสัญญาผูกมัดที่เป็นไปได้ (เพราะฉันคิดไม่ออกว่าคุณจะใช้สิ่งนี้อย่างไร)

ดังที่คุณทราบ Bob แผนความมุ่งมั่นคือสิ่งที่อลิซมีความลับ เธอเผยแพร่คำมั่นสัญญาต่อความลับ ('คำมั่นสัญญาต่อความลับ') และหลังจากนั้น เธอ 'เปิด' คำมั่นสัญญา เปิดเผยความลับ

มีคุณสมบัติด้านความปลอดภัยที่น่าสนใจสองอย่างในโครงร่างข้อผูกพัน:

• ซ่อน; บ๊อบที่เห็นความมุ่งมั่นไม่สามารถบอกได้ว่าความลับคืออะไร (แม้ว่าเขาจะเดาได้ก็ตาม)
• ผูกพัน; เมื่ออลิซเปิดข้อผูกมัด เธอต้องเปิดตามค่าที่เธอคิดไว้ตอนที่สร้างข้อผูกมัด (นั่นคือ เธอไม่สามารถเปิดให้กับค่าใดค่าหนึ่งจากสองค่าที่แตกต่างกันในเวลาเปิด)

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

ตอนนี้มีแผนการผูกมัดมาตรฐานสองแบบ:

• ความมุ่งมั่นตามแฮชที่อลิซใช้ความลับ $S$ และค่าสุ่ม $R$ และเผยแพร่ปณิธาน $\text{แฮช}( S || R )$สำหรับฟังก์ชันแฮชที่ป้องกันการชนกัน $\text{แฮช}$; เพื่อเปิดมันเธอเผยแพร่ $S$ และ $R$. สิ่งนี้กลายเป็นการเชื่อมโยงทางคอมพิวเตอร์ (ขึ้นอยู่กับความต้านทานการชนกันของแฮชและสมมติว่าความยาวของ S หรือ R เป็นที่รู้จักกันดี) และการซ่อนทางสถิติ (สมมติว่า $R$ มีความยาวเพียงพอ และเป็นสมมติฐานที่ไม่เป็นมาตรฐานแต่เข้าใจได้ง่ายเกี่ยวกับฟังก์ชันแฮช)

• ความมุ่งมั่นของ Pedersen ที่เรามีเครื่องกำเนิดสองเครื่องที่แตกต่างกัน $g$ และ $h$ (ที่ไม่รู้จักความสัมพันธ์) ของบางกลุ่มที่ปัญหาล็อกไม่ต่อเนื่องยาก; เพื่อมอบคุณค่า $S$เธอเลือกค่าสุ่ม $R$ และเผยแพร่ $ก^ช^R$; เพื่อเปิดมันเธอเผยแพร่ $S$ และ $R$. สิ่งนี้กลายเป็นการซ่อนที่สมบูรณ์แบบและการผูกมัดด้วยการคำนวณ (ลดปัญหา DLog)

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

ตอนนี้ไปที่โครงการของคุณ:

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

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

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

ฉันจะชี้ให้เห็นปัญหาบางอย่างที่ฉันเห็นเกี่ยวกับสิ่งนี้ สิ่งเหล่านี้อาจผิด แต่ฉันก็ยังพบว่ามันน่าสนใจ

• การตั้งค่าข้อมูลของคุณให้เท่ากับ (หรือแสดง) ด้วยจำนวนเฉพาะนั้นไม่ใช่เรื่องง่ายเสมอไป เมื่อได้รับข้อความบางอย่างที่เข้ารหัสเป็นไพรม์ 1 สิ่งที่จะหยุดข้อความอื่นที่มีความยาวเท่ากันไม่ให้เข้ารหัสเป็นไพรม์เดียวกัน (พื้นที่ข้อความขนาดเล็กอาจจะ?)

• การถอดรหัสจะทำงานอย่างไรที่นี่...

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

ฉันยังใหม่กับการเข้ารหัส ดังนั้นเป็นไปได้ว่าฉันเข้าใจผิดในข้อสันนิษฐานข้อใดข้อหนึ่ง โปรดอย่าลังเลที่จะโทรหาฉัน และยังคงขอแสดงความยินดีกับแนวคิดที่น่าสนใจ!