การใช้ปัจจัยร่วมเพื่อค้นหาจุดฐานสำหรับเหตุผลด้านประสิทธิภาพเท่านั้นหรือไม่

สำหรับการเข้ารหัสเส้นโค้งวงรี ขั้นตอนการค้นหาจุดฐานที่สร้างกลุ่มย่อยที่มีลำดับ $n$ เป็น:

1. คำนวณการสั่งซื้อ $N$ ของเส้นโค้งวงรี (ใช้ของ Schoof)
2. เลือก $n$. $n$ ต้องเป็นจำนวนเฉพาะและตัวหารของ $N$
3. คำนวณโคแฟกเตอร์ $h = \frac{N}{n}$
4. เลือกจุดสุ่ม $พี$ บนทางโค้ง
5. คำนวณ $G = hP$
6. ถ้า $G$ เป็น 0 แล้วกลับไปที่ขั้นตอนที่ 4 มิฉะนั้น คุณพบตัวสร้างที่มีลำดับ $n$ และโคแฟกเตอร์ $h$

แหล่งที่มา

จุดประสงค์ของโคแฟกเตอร์ในที่นี้คือเพื่อเพิ่มประสิทธิภาพในการหากลุ่มย่อยขนาดใหญ่เท่านั้นใช่หรือไม่?

ฉันคิดว่าถ้าคุณไม่ได้ใช้ co-factor และพยายามคำนวณแบบ brute-force แทนว่าจุดสุ่ม $พี$เป็นตัวกำเนิดสำหรับกลุ่มย่อยที่มีขนาด $n$ คุณจะต้องทำ $n$ การทำซ้ำซึ่งจะเป็นไปไม่ได้ในคอมพิวเตอร์สมัยใหม่ แต่ฉันต้องการยืนยัน

แก้ไข: ย่อหน้าสุดท้ายของฉันผิด b/c เราสามารถใช้กำลังสองซ้ำๆ เพื่อคำนวณได้ $G = nP$

นี่เป็นผลลัพธ์เชิงประจักษ์เพื่อเสริมคำตอบของ Poncho

ใช้ Curve25519 ซึ่งมีปัจจัยร่วม $8$ เป็นคำสั่ง $n$ ของปัจจัยกลุ่มดังเช่น

$\small{n = 2^3 * 7237005577332262213973186563042994240857116359379907606001950938285454250989}$

• $h = 8 $
• $q = n/8$

เราใช้ SageMath และ SageMath สุ่ม_องค์ประกอบ ซึ่งทำหน้าที่ มันอาจส่งคืนองค์ประกอบเอกลักษณ์ $\mathcal{O}$ ของเส้นโค้ง (โอกาสได้น้อยมาก) , บน Curve25519 $\คณิตศาสตร์แคล{O} = (0:1:0)$ ในรูปแบบไวเออร์สตราส

เวลานำเข้า

def สุ่มBasePointByCofactor (E, เอกลักษณ์, ปัจจัยร่วม):
    
    s = เวลา เวลา ()
    ci = 0
    n = E.คำสั่ง()
    สำหรับผมในช่วง (1,10000):
        P = E.random_element()
        ถ้า cofactor*P != ตัวตน:
            ci = ci +1
    จ = เวลา เวลา ()
    พิมพ์ ("เวลาที่ผ่านไปบน RandomBasePointByCofactor", e-s)
    กลับ (ci)
        
def RandomBasePointByOrder (E, ตัวตน, ปัจจัยร่วม):
    
    s = เวลา เวลา ()
    ci = 0
    n = จำนวนเต็ม (E.order() / ตัวประกอบ)
    สำหรับผมในช่วง (1,10000):
        P = E.random_element()
        ถ้า n*P == ตัวตน:
            ci = ci +1

    จ = เวลา เวลา ()
    พิมพ์ ("เวลาที่ผ่านไปบน RandomBasePointByOrder", e-s)
    กลับ (ci)    

พี = 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffff
K = GF(พี)
ก = K(0x76d06)
B = K(0x01)
E = EllipticCurve(K, ((3 - A^2)/(3 * B^2), (2 * A^3 - 9 * A)/(27 * B^3)))

IP = E((0,1,0))
ผูกพัน = 10,000

พิมพ์ (" จำนวนเครื่องกำเนิดไฟฟ้าที่พบ =" , RandomBasePointByCofactor(E,IP,8), "/", ผูกไว้)

พิมพ์ (" จำนวนตัวสร้างที่พบ =", RandomBasePointByOrder (E, IP,8),"/", ผูกไว้)

ผลลัพธ์ตัวอย่างคือ

เวลาที่ผ่านไปบน RandomBasePointByCofactor 1.9164307117462158
 จำนวนเครื่องกำเนิดไฟฟ้าที่พบ = 9999 / 10,000
เวลาที่ผ่านไปบน RandomBasePointByOrder 64.77565383911133
 จำนวนเครื่องกำเนิดไฟฟ้าที่พบ = 1267 / 10,000

ดังนั้น

• วิธี cofactor เร็วกว่า ~ 32 เท่าเร็วกว่าในการทดลอง

  เราสามารถอธิบายสิ่งนี้ด้วยคำง่ายๆ เช่น $8$ ต้องการการเสแสร้ง 4 ครั้งและการเพิ่ม 1 ครั้ง ในขณะที่ $n$ ต้องการการเสแสร้ง 251 ครั้งและการเพิ่ม 125 ครั้งด้วยความไร้เดียงสา ดับเบิลและอัลกอริทึม. สิ่งนี้ให้การคำนวณเพิ่มขึ้น ~ 75 เท่าหากเราถือว่าการเพิ่มเป็นสองเท่าและการเพิ่มเติมมีความเร็วเท่ากันซึ่งไม่ใช่

• วิธีปัจจัยร่วมสร้างเครื่องกำเนิดไฟฟ้ามากกว่าวิธีการสั่งซื้อตั้งแต่ $1/8$ ขององค์ประกอบสุ่มจาก $8\cdot q$ ตกอยู่ในนายกรัฐมนตรีขนาดใหญ่ $คิว$ ของ Curve25519.

ดังนั้นวิธีโคแฟกเตอร์จึงเป็นที่นิยม