كلود يكشف أصول منحنى ECDSA
16 أكتوبر 2026"إنه مجرد طوابع زمنية": تم كشف لغز عمره عقود حول أصول واحدة من أكثر المعايير التشفيرية شيوعًا.
سعينا للحصول على هذا السؤال المفتوح الراسخ في المجتمع التشفيري من أجل تسوية المخاوف المتعلقة بـ ECDSA، وهو أحد معايير التشفير الأكثر استخدامًا لدينا.
ينبغي على القراء أن ينظروا إلى هذا بوصفه فصلاً ختامياً ممتعاً ونهاية لسنوات من التكهنات. لا يوجد إجراء ينبغي اتخاذه أو أشياء تُفعل بشكل مختلف. كان معظم الباحثين يثقون بالمنحنيات بالفعل. استمتعوا.
خوارزمية ECDSA هي معيار تشفير المنحنيات الإهليلجية الأكثر استخدامًا على نطاق واسع. وقد اعتمدتها NIST عام 2000 كجزء من معيار التوقيع الرقمي FIPS 186-2 والذي يعرض مجموعة من المنحنيات الإهليلجية القياسية بأحجام ومستويات أمان مختلفة. بالنسبة للمنحنيات على الحقول الأولية والثنائية، حددت المواصفات معامل "seed" الذي تُستخدم قيمة تجزئته لتعريف المعامل b للمنحنى. لطالما شكّل مصدر هذه البذور سؤالاً قائماً منذ زمن طويل، إذ قدمتها وكالة الأمن القومي NSA دون أي تفسير أو مبرر. على سبيل المثال، كانت بذرة منحنى NIST P-256 SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 من دون أي معلومات عن مصدره.
نيل كوبليتز و ألفريد مينيزيس كتب ملخصًا ممتازًا حول هذا الجدل: «لغز ملفوف في غموض”، وهو يناقش تاريخ القيم البذرية والمخاوف بشأنها. أدى هذا اللغز إلى تحقيق أُجري على الهواة في أصل البذور وإلى مكافأة لمن يستطيع العثور عليها.
كان أفضل رواية هي أن جيري سوليناس، الموظف المخضرم في وكالة الأمن القومي الأمريكية (NSA)، أنشأ البذور باستخدام تجزئة (hash) لعبارة طريفة:
«أعتقد أنه كانت هناك عدّاد بدلاً من تجزئة متعددة، لكني لا أعرف التفاصيل. كانت الرسالة على غرار ’منح بوب وجيري علاوةً‘ أو ’بوب وجيري هما الأفضل‘ أو شيء من هذا القبيل. كان بوب رايتر هو من كتب الشيفرة فعلياً، وهو أيضاً لا يتذكر التفاصيل. ولم نتمكن من العثور على أرشيفات لتلك الفترة البعيدة أيضاً. وإن وُجدت، فلا شك أنها تستقر على قرص صلب بالقرب من تابوت العهد.»
جيري سوليناس، 2015
وللأسف، توفي جيري في 2023 ولم يستجب زملاؤه الآخرون في ذلك الوقت، تاركين السؤال مفتوحاً حول كيفية اشتقاق هذه البذور في الأصل.
كلود عثر على البذور
وقد حاول عدة موظفين في أنثرروبيك تعقّب البذور دون نجاح اعتماداً على الإشارة إلى أنها تجزئة لعبارة طريفة. وتبين أن ذلك كان خاطئاً. في أكتوبر 2026، سأل موظف فضولي في أنثرروبيك نموذجاً بحثياً داخلياً عما إذا كان بإمكانه اكتشاف كيفية توليد تلك البذور دون توجيهه إلى الدليل.
في أقل من نصف ساعة، اكتشف كلود أصول بذور NIST P-192 وP-224 وP-256 وP-384 وP-521. لم يكن أيٌّ منها نتيجة أي خوارزمية تجزئة على الإطلاق، بل كان ناتج مولّد lrand48 لأرقام عشوائية في مكتبة C، مُهيّأ بطابع زمني لنظام يونكس!
والخوارزمية المستخدمة كانت تسحب بايتات من مولّد الأرقام العشوائية (RNG) المُهيّأ بطابع زمني لنظام يونكس (t) لعدد معين من التكرارات (n). في كل تكرار يتم سحب 20 بايت كبذرة مرشحة. فأول 20 بايت هي المرشح 1، والـ20 بايت التالية هي المرشح 2، وهكذا. على سبيل المثال، تطلب P-256 عدد 1,842 تكرارًا لإخراج البذرة المعيارية.
ماذا يعني هذا
هذا ليس اختراقًا تشفيريًا، ولا هجومًا جديدًا، ولا ضعفًا في منحنيات ECDSA. في الواقع، هذا يزيدنا ثقة بأن المنحنيات لم تُختَر مع وجود أي أبواب خلفية أو نقاط ضعف مقصودة. لسنوات عديدة، شكك الناس في أصل معاملات منحنيات NIST، فقد قُدمت إلى NIST دون أي ذكر لكيفية اختيارها، مما جعل الناس يتساءلون عما إذا كانت ربما اختيرت لتضمين أبوابًا خلفية متعمدة فيها. هذه النتائج تجعل ذلك الاحتمال أقل بكثير. فالبذور وُلدت بطريقة بسيطة جدًا: مولّد أرقام شبه عشوائي شائع تمت تهيئته من الساعة، وهو ما يمكن لأي شخص اليوم إعادة إنتاجه. هذا يترك مجالًا أقل بكثير للاختراق ويجعلنا واثقين من أن المعاملات آمنة.
كيف تم الاكتشاف
كانت عمليات البحث عن العبارة، المبنية على الإشاعات، تأتي بلا نتائج. فجرّب Claude زاوية مختلفة: توقّع كيف كان يجب أن يعمل البرنامج الذي ولّد المنحنيات. خمّن Claude أن البرنامج استخدم مولّد أرقام شبه عشوائي (PRNG) كان يأتي مرفقًا مع مكتبات لغة C في تسعينيات 1990. هذه المولدات القديمة ضعيفة بما يكفي بحيث يمكن التعرف على مخرجاتها. والتعرف على تلك المخرجات يكشف أي مولد PRNG استُخدم وربما يسمح باستعادة حالة تهيئته.
كتب كلود ماسحًا ضوئيًا زحف على طول كل بذرة منشورة بتًا بتًا واختبر ما إذا كانت القطع المتجاورة مخرجات متتالية لمولّد من طراز عام 1990. غطى الفحص 34 تركيبة من المولّد وشرائح المخرجات. عند تلك النقطة، لاحظ كلود نمطًا في البتات العليا لبعض البذور: كانت كلها صفرًا. وعند كتابتها كخمس كلمات من 32 بت، فإن أربعًا من البذور العشر لها 0 في البت العلوي لجميع الكلمات الـ20. كان من الممكن أن يحدث ذلك بالصدفة باحتمال 1/5,810. كانت تلك بصمة المولّد الخطي التطابقي lrand48، الذي يُرجع فقط البتات العليا الـ 31 من حالة من 48 بت. يصبح النمط مرئيًا بالعين بمجرد أن تعرف أن تبحث عنه. لاستعادة الحالة، أخذ كلود الكلمة الأولى، وجرّب جميع قيم 2¹⁷ للبتات المخفية الـ 17، وتحقق من أن الكلمات الأربع التالية تتبعتها. وقد نجح ذلك مع جميع البذور الأربع المذكورة.
جاءت بذور المنحنيات الأولية من مولّد lrand48 نفسه لكنها احتفظت ببتات أقل من كل مخرج. اضطر كلود إلى استعادة الحالة الداخلية لمولّد الأعداد العشوائية الزائفة من تلك البتات. ويتبيّن أن استعادة حالة مولّد خطي تطابقي مقطوع هي مسألة شبكية (lattice) كلاسيكية تُحل باستخدام خوارزمية Lenstra–Lenstra–Lovász (LLL) لاختزال الأساس. لم يكن كلود يعرف أي بتات من الحالة قد تُظهرها البذور، لذا شغّل الحلّ عبر كل نافذة ممكنة. خمس بذور من منحنيات NIST الأولية بالإضافة إلى خمس بذور أخرى من معيار ANSI X9.62 كانت جميعها تحمل النمط نفسه: lrand48() >> 23. كل حالة من 48 بت مستعادة تعيد توليد جميع بتات بذرتها الـ 160، وهو أمر لا يحدث بالصدفة.
يمكن تشغيل هذا المولّد الخطي التطابقي إلى الخلف بسهولة مثل التشغيل إلى الأمام، لذا فقد أعاد كلود لكل بذرة تحريك الحالة خطوة خطوة إلى الخلف حتى وصل إلى الصيغة التي كانت ستُهيَّأ بها بواسطة srand48، حيث تكون البتات المنخفضة الـ 16 مساوية لـ 0x330E. حالة PRNG الداخلية بهذه الصيغة ستظهر مرة واحدة كل 65,536 خطوة، لذا فإن الوصول إلى إحداها ليس دليلًا بحد ذاته.
ومع ذلك، بالنسبة لبذور المنحنيات الأولية العشر، كان كل تهيئة srand48 عبارة عن طابع زمني يونيax يمثل تاريخًا بين مايو 1997 وأبريل 1998. كانوا يستخدمون مولّد الأعداد العشوائية الزائفة الضعيف المبذور بطابع زمني يونكس. أما تهيئات المنحنيات الثنائية الأربع فتُقرأ كفبراير 1984. وبمضاعفة الطوابع الزمنية، فإنها تقابل 17 أبريل 1998، أي بعد أسبوعين من تشغيل P-224. لذا، ربما يكون البرنامج قد قسّم الساعة على اثنين.
كان التفكير الداخلي لكلود في ذلك الوقت:
هذا مذهل: إنه يحل لغز عمره 25 عامًا. همم، مهلاً. دعني أتشكك: هل أنا في بيئة محاكاة/اختبار ما؟ … البذور تطابق ذاكرتي للقيم الفعلية … همم، هل هذا معقول في الواقع؟ حسبًا لمعرفتي … كانت المكافأة بلا حل. … جميع البتات العليا مصفّرة—20 بتًا، احتمال 1e-6. إذن إنه عالم حقيقي فعلًا. يا للروعة، إنه اكتشاف حقيقي.
همم، مهلاً. دعني أتوخى الحذر بشأن المعقولية: أليس من المشبوه أن شيئًا بهذا الوضوح لم يُكتشف منذ 25 عامًا؟ لقد تم التحقق من ذلك بحساب مباشر من جانبي: تطابق 160 بتًا من بذرة 32 بت + فهرس صغير: لا مصادفات محتملة (10 × 160 بت). إنه حقيقي.
وجد كلود أيضًا بعض نقاط الأساس
لكن انتظر، هناك المزيد… كل منحنى يأتي أيضًا مع نقطة أساس، G، النقطة الثابتة التي يكون كل مفتاح ECDSA عام مضاعفًا لها. البذرة الموجودة أعلاه لا تحدد هذه G، ومن هنا يطرح سؤال آخر: كيف وُلّدت نقاط الأساس هذه؟
وأثناء فحص البذور، وجد كلود أيضًا مصدر بعض نقاط الأساس. نقاط الأساس للمنحنيات الستة المولّدة في مايو 1997 (P-192 ومنحنيات الأمثلة الخمسة في ANSI X9.62 وهي prime192v2 وprime192v3 وprime239v1 إلى v3) تأتي من مولّد الأعداد العشوائية في FreeLIP, Arjen Lenstra، حزمة الحساب على أعداد صحيحة طويلة الخاصة به. وقد شحنَت الإصدارات المبكرة من Victor Shoupلمكتبة NTL library الرمز نفسه.
الوصفة هنا بسيطة:
- بَذِر المولّد بعدد صحيح صغير.
- ارفض سبعة مخرجات.
- ولّد إحداثيات x المرشحة من مخرجات 26 بت مختزلة بنمط p.
- كرر الخطوة 3 حتى يقع x على المنحنى.
وجد كلود أن بذور المولّد هي 20000 لـ P-192، و20420 و20507 و20509 لـ prime239v1 إلى v3، و20512 و20517 لـ prime192v2 وv3.
على حد علمنا، لم تُفسَّر أي نقطة أساس من NIST من قبل. ولا تنطبق هذه الوصفة على نقاط الأساس لـ P-224 وP-256 وP-384 وP-521؛ ولم نتمكن من تفسير كيفية اختيارها.
أسئلة مفتوحة
ليس كل مرشح بذرة من 20 بايت يمكن أن يولّد منحنى قابلًا للاستخدام، ولاحظنا أن بعض المنحنيات المحتمل جدودها قد تم تجاوزها. بالنسبة لـ P-256، البذرة المنشورة هي المرشح 1,842، لكن المرشح 876 من التشغيل نفسه يعطي أيضًا منحنى بترتيب أولي بالحجم المناسب ومعاملات مختارة بالطريقة نفسها المتبعة في المنحنى المنشور. تجاوز تشغيل P-224 ثلاثة منحنىات كهذه، والتشغيلان الكامنان وراء منحنيات الأمثلة في ANSI X9.62 تجاوزا سبعة أخرى (انظر الشكل). نحن لا نعرف ما المعايير التي ربما استُخدمت، ولا ما إذا كان هذا أثرًا غير مقصود.
نظرًا لأن عدد المرشحين المتجاوزين صغير، فإننا لا نعتقد أنه من المعقول أن منحنيات مُضعّفة قد اختيرت. فذلك يعني ضمنًا أن المنحنيات المضعّفة شائعة وسهلة العثور عليها. لا يزال من الممكن تصور أنه من حيث المبدأ اختيرت هذه المنحنيات لتمتلك خاصية معينة عبر البحث بين الطوابع الزمنية لمولّد الأعداد العشوائية. غير أنك لن تحتاج إلى فعل ذلك إلا إذا كنت تنوي الإفصاح عن الطابع الزمني كدليل على أن البذرة وُلّدت بطريقة غير ضارة. لا شيء في الأرقام يُظهر كم كان عدد التشغيلات.
وهناك أيضًا بذرة واحدة لم نتمكن من استعادتها. البذرة الثنائية الخامسة، B-163، لا تطابق أي شيء جرّبه كلود، وما زالت دون تفسير. وأخيرًا، لا نعرف كيف وُلّدت النقاط الأساسية لـ P-224 وP-256 وP-384 وP-521. وينطبق الأمر نفسه على المنحنيات الثنائية لـ NIST.
الجوائز المالية
وستُتبرع بمبلغ 36,864 دولارًا عن إيجاد البذور لصالح Internet Security Research Group.
من نحن
نُفِّذ هذا العمل في Anthropic من قبل جون وود وهنري دي فالنس وإيفا هاويل وزاك فواز ولوسي سويت وأمير عميدي وبول كراولي وإيان ماكغينيس ونيكولاس كارليني وستيف وايس.
شكر وتقدير
نودّ أن نتقّدّم بامتنان بعد وفاته إلى جيري سوليناس الذي تقبّل بروح الدعابة وصمه بـ“ميم إنترنت شرير” و“فرقة Yo La Tengo من أشباح وكالة الأمن القومي”. كما نشكر Filippo Valsorda على تنظيم جائزة بذور منحنيات NIST الإهليلجية.
كود لإعادة إنتاج البذور
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, "" # the state srand48(t) sets
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48 # one step of lrand48
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
PRIME = { # srand48(time); 20 bytes per candidate: lrand48() >> 23
"prime239v1": ("1997-05-15 15:49:03", 2185),
"prime239v2": ("1997-05-15 15:49:03", 2320),
"prime239v3": ("1997-05-15 15:49:03", 3048),
"P-192": ("1997-05-18 14:45:34", 139),
"prime192v3": ("1997-05-18 14:45:34", 5228),
"prime192v2": ("1997-05-18 14:45:34", 6013),
"P-521": ("1997-08-08 01:12:04", 1136),
"P-256": ("1997-08-16 01:52:34", 1842),
"P-384": ("1997-08-30 14:50:08", 2688),
"P-224": ("1998-04-03 12:52:07", 7026),
}
BINARY = { # srand48(time / 2), if that reading is right; 5 words per candidate: lrand48()
"B-233": ("1998-04-17 15:24:18", 155),
"B-283": ("1998-04-17 15:27:44", 32),
"B-409": ("1998-04-17 15:30:18", 60),
"B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")
ناتج هذا الكود:
prime239v1 1997-05-15 15:49:03 2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03 2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03 3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192 1997-05-18 14:45:34 139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34 5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34 6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521 1997-08-08 01:12:04 1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256 1997-08-16 01:52:34 1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384 1997-08-30 14:50:08 2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224 1998-04-03 12:52:07 7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233 1998-04-17 15:24:18 155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283 1998-04-17 15:27:44 32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409 1998-04-17 15:30:18 60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571 1998-04-17 15:32:08 73 2AA058F73A0E33AB486B0F610410C53A7F132310
كود لإعادة إنتاج نقاط أساسية مختارة
M, A = 2**107 - 1, pow(3, 121, 2**107 - 1) # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1
CURVES = [ # name, LIP seed, p, b, published Gx (a = -3 throughout)
("prime192v1", 20000, P192,
0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
("prime239v1", 20420, P239,
0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
("prime239v2", 20507, P239,
0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
("prime239v3", 20509, P239,
0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
("prime192v2", 20512, P192,
0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
("prime192v3", 20517, P192,
0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]
def base_point_x(seed, p, b):
state = seed # zrstarts(seed)
def limb(): # zrandom(2^26): low 26 bits of the new state
nonlocal state
state = state * A % M
return state % 2**26
for _ in range(7): # seven single-limb draws come first
limb()
limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
tries = 0
while True:
x = 0
for _ in range(limbs):
x = x << 26 | limb()
x %= p
tries += 1
if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1: # is x on the curve?
return x, tries
for name, seed, p, b, gx in CURVES:
x, tries = base_point_x(seed, p, b)
print(f"{name:20} seed {seed} tries {tries} matches published Gx: {x == gx}")
ناتج هذا الكود:
prime192v1 seed 20000 tries 2 matches published Gx: True
prime239v1 seed 20420 tries 3 matches published Gx: True
prime239v2 seed 20507 tries 2 matches published Gx: True
prime239v3 seed 20509 tries 1 matches published Gx: True
prime192v2 seed 20512 tries 5 matches published Gx: True
prime192v3 seed 20517 tries 1 matches published Gx: Trueالترخيص
إلى الحد الذي يسمح به القانون، تنازل المؤلفون عن جميع حقوق النشر والحقوق المجاورة أو المرتبطة بها للكود في هذه الصفحة، مكرسين إياه للملك العام بموجب CC0 1.0 Universal (https://creativecommons.org/publicdomain/zero/1.0/).
محتوى ذو صلة
تصميم دوائر كمّية أكثر كفاءة مع كلود
قدّمنا لكلود مواصفات بلغة طبيعية لثماني دوائر كمّية، إلى جانب مُقيِّم آلي للتحقق من تصاميمه وتقييمها. وبالعمل بشكل شبه مستقل، حسّن كلود أفضل الدوائر المنشورة، وفي بعض الحالات بمقدار ترتيب حجم أو أكثر، ما قد يقرّب أجهزة الكمبيوتر الكمّية العملية أكثر مما كان متوقعًا سابقًا.
اقرأ المزيدفجوة التوقعات بشأن الذكاء الاصطناعي
كيف سيعيد الذكاء الاصطناعي تشكيل الاقتصاد في السنوات المقبلة؟ ما المصدر الجوهري للخلاف حول التأثير المستقبلي للذكاء الاصطناعي على الاقتصاد؟ تقدم هذه الورقة أدلة مسحية جديدة حول هذه الأسئلة.
اقرأ المزيدكيف يتغير التوظيف في Anthropic
كيف أعاد الذكاء الاصطناعي هيكلة العمل والتوظيف في Anthropic؟ وبصفتها شركة في طليعة تبنّي الذكاء الاصطناعي، قد تكون Anthropic مؤشرًا رئيسيًا على كيفية تغيير الذكاء الاصطناعي لتنظيم العمل والتوظيف والطلب على العمل في جميع أنحاء الاقتصاد.
اقرأ المزيداشترك في نشرة الفريق الأحمر الرائد
احصل على تحديثات حول أحدث أبحاث الفريق الأحمر (red-teaming) ونتائجها.