حجم جدول قوس قزح

الخطوة 1: فهم جدول قوس قزح. جدول قوس قزح هو هيكل بيانات يستخدم في كسر كلمات المرور المخزنة بصيغة التجزئة (hash). يعتمد على تقنية المفاضلة بين الزمن والذاكرة (time-memory trade-off). يتم إنشاء الجدول باستخدام سلاسل من التجزئات (hashes) حيث كل سلسلة تبدأ بكلمة مرور محتملة وتنتهي بكلمة مرور أخرى بعد تطبيق دوال اختزال (reduction functions). الهدف هو تقليل حجم التخزين اللازم مقارنة بجداول البحث المباشرة. لتقدير حجم جدول قوس قزح تحتاج إلى ثلاثة معاملات للحجم: طول السلسلة (chain length)، عدد السلاسل (number of chains)، وحجم التجزئة (hash size) بالبت؛ ويُضاف إليها مساحة كلمات المرور M لتقدير التغطية وحدها.

الخطوة 2: إدخال طول السلسلة (chain length). طول السلسلة هو عدد مرات تطبيق دالة التجزئة ودالة الاختزال بالتناوب على طول السلسلة. كلما زاد طول السلسلة، زادت التغطية (coverage) لمساحة كلمات المرور، ولكن على حساب وقت الحساب (وقت الكسر) وربما تقليل احتمال النجاح. أدخل قيمة طول السلسلة (مثل 1000 أو 10000). عادةً ما تكون الأطوال في حدود آلاف إلى مئات الآلاف.

الخطوة 3: إدخال عدد السلاسل (number of chains). عدد السلاسل هو عدد نقاط البداية المختلفة المستخدمة في الجدول. كل سلسلة تبدأ بكلمة مرور عشوائية وتنتهي بنقطة نهاية (endpoint). عدد السلاسل مضروباً في طول السلسلة يعطي إجمالي عدد الخطوات المحسوبة، لكن التخزين الفعلي هو فقط نقاط البداية والنهاية لكل سلسلة. كلما زاد عدد السلاسل، زاد حجم الجدول خطياً.

الخطوة 4: إدخال حجم التجزئة (hash size) بالبت لا بالبايت: حجم التجزئة هو عدد البتات الناتجة عن دالة التجزئة المستخدمة (مثل MD5 = 128 بت، SHA-1 = 160 بت، SHA-256 = 256 بت). هذا يحدد مقدار الذاكرة المطلوبة لتخزين نقطة نهاية واحدة (أو نقطة بداية) بقسمة عدد البتات على 8. أدخل حجم التجزئة بالبت (مثلاً 128).

الخطوة 5: حساب حجم جدول قوس قزح. الصيغة الأساسية: حجم الجدول (بالبايت) = عدد السلاسل * (حجم نقطة البداية + حجم نقطة النهاية). عادةً ما يتم تخزين نقطة البداية والنهاية بنفس حجم التجزئة (أو أقل لتوفير المساحة). لذا يصبح الحجم = عدد السلاسل * 2 * (hashSize / 8) بايت، أي أن طول السلسلة لا يدخل في التخزين إطلاقًا لأنه يحدد عدد الخطوات المحسوبة لا كمية المحفوظات. لكن في الممارسة، غالباً ما يتم تخزين نقطة النهاية فقط (بما أن نقطة البداية يمكن اشتقاقها من الترتيب أو تخزينها بطريقة مضغوطة). في هذه الآلة الحاسبة، نفترض تخزين نقطة البداية ونقطة النهاية كما تنص هذه الخطوة. ملاحظة على الوحدة: المخرَج يقسم البايتات على 1024×1024، أي أنه ميجابايت ثنائي (MiB)؛ لذلك 3,200,000 بايت تظهر كـ 3.05 وليس 3.2 (وهو الرقم العشري المذكور في المثال الأول).

الخطوة 6: تقدير التغطية. التغطية التقريبية = (عدد السلاسل × طول السلسلة) ÷ مساحة كلمات المرور M، طالما كان البسط أصغر بكثير من M كما يقرّر السؤال الرابع. لذلك تطلب الحاسبة قيمة M وتعرض الناتج في تفصيل 'Coverage estimate (N x L / M)'، وتعرض أيضاً أقصى عدد سلاسل يسع في 1 جيجابايت ثنائي (1,073,741,824 بايت) لتطبيق حدود الذاكرة كما في المثال الثاني.