وظيفة الباب الخلفي

في علوم الحاسوب النظرية وعلم التشفير ، تُعرف دالة الباب الخلفي بأنها دالة يسهل حسابها في اتجاه واحد، ولكن يصعب حسابها في الاتجاه المعاكس (إيجاد معكوسها ) دون معلومات خاصة تُسمى "الباب الخلفي". تُعد دوال الباب الخلفي حالة خاصة من الدوال أحادية الاتجاه ، وتُستخدم على نطاق واسع في التشفير بالمفتاح العام . ^{[ 2 ]}

رياضيًا، إذا كانت f دالة ذات باب سري، فإنه يوجد معلومة سرية t ، بحيث إذا عُلمت f ( x ) و t ، يسهل حساب x . لنفترض وجود قفل ومفتاحه. من السهل تغيير حالة القفل من مفتوح إلى مغلق دون استخدام المفتاح، وذلك بدفع حلقة القفل داخل آلية القفل. مع ذلك، يتطلب فتح القفل بسهولة استخدام المفتاح. هنا، المفتاح t هو الباب السري، والقفل هو دالة الباب السري.

مثال على معضلة رياضية بسيطة: "6895601 هو حاصل ضرب عددين أوليين. ما هما هذان العددان؟" الحل التقليدي هو قسمة 6895601 على العديد من الأعداد الأولية حتى الوصول إلى الإجابة. ولكن، إذا علمنا أن 1931 هو أحد هذين العددين، فيمكننا إيجاد الإجابة ببساطة عن طريق إدخال "6895601 ÷ 1931" في أي آلة حاسبة. هذا المثال ليس مثالًا دقيقًا لمعضلة رياضية - فالحواسيب الحديثة قادرة على تخمين جميع الإجابات المحتملة في ثانية واحدة - ولكن يمكن تحسين هذه المسألة باستخدام حاصل ضرب عددين أوليين أكبر بكثير .

برزت دوال الباب الخلفي في علم التشفير في منتصف سبعينيات القرن العشرين مع نشر تقنيات التشفير غير المتماثل (أو التشفير بالمفتاح العام) من قِبل ديفي وهيلمان وميركل . في الواقع، صاغ ديفي وهيلمان (1976) هذا المصطلح. وقد اقتُرحت عدة فئات من الدوال، وسرعان ما اتضح أن إيجاد دوال الباب الخلفي أصعب مما كان يُعتقد في البداية. على سبيل المثال، كان أحد الاقتراحات المبكرة هو استخدام مخططات تعتمد على مسألة مجموع المجموعات الجزئية ، ولكن سرعان ما تبين عدم ملاءمة هذا الاقتراح.

اعتبارًا من عام 2004تُعدّ عائلتا دوال RSA و Rabin من أشهر دوال الباب الخلفي المرشحة . تُكتب كلتاهما على شكل أسّ بتردد عدد مركّب، وترتبطان بمسألة التحليل إلى عوامل أولية .

لا يُعرف أن الدوال المتعلقة بصعوبة مسألة اللوغاريتم المنفصل (سواء كان ذلك بتردد عدد أولي أو في مجموعة معرفة على منحنى إهليلجي ) هي دوال ذات باب خلفي، لأنه لا توجد معلومات "باب خلفي" معروفة حول المجموعة التي تُمكّن من الحساب الفعال للوغاريتمات المنفصلة.

في علم التشفير، يُشير مصطلح "الباب الخلفي" إلى المعنى المحدد المذكور آنفًا، ولا ينبغي الخلط بينه وبين " الباب الخفي" (إذ يُستخدم المصطلحان غالبًا بشكل متبادل، وهذا خطأ). الباب الخفي هو آلية مُتعمّدة تُضاف إلى خوارزمية تشفير (مثل خوارزمية توليد أزواج المفاتيح، أو خوارزمية التوقيع الرقمي، إلخ) أو نظام تشغيل، على سبيل المثال، تسمح لطرف أو أكثر من الأطراف غير المصرح لها بتجاوز أو اختراق أمان النظام بطريقة ما.

تعريف

دالة الباب الخلفي هي مجموعة من الدوال أحادية الاتجاه { f _k : D _k → R _k } ( k ∈ K )، حيث تكون جميع K و D _k و R _k مجموعات جزئية من السلاسل الثنائية {0, 1} ^* ، والتي تحقق الشروط التالية:

توجد خوارزمية أخذ عينات احتمالية متعددة الحدود (PPT) تُسمى Gen(1 ⁿ ) = ( k , t _k ) حيث k ∈ K ∩ {0, 1} ⁿ و t _k ∈ {0, 1} ^* تحقق الشرط | t _k | < p ( n )، حيث p دالة متعددة الحدود. يُطلق على كل قيمة t _k اسم " الباب الخلفي" المقابل لـ k . ويمكن أخذ عينات من كل باب خلفي بكفاءة.
بفرض المدخل k ، توجد أيضًا خوارزمية PPT تُخرج x ∈ D _k . أي أنه يمكن أخذ عينات من كل D _{k بكفاءة.}
لكل k ∈ K ، توجد خوارزمية PPT التي تحسب f _k بشكل صحيح .
لكل k ∈ K ، توجد خوارزمية PPT A st لأي x ∈ D _k ، ليكن y = A ( k , f _k ( x ), t _k )، عندئذٍ يكون لدينا f _k ( y ) = f _k ( x ). أي أنه بمعلومية الباب الخلفي، يسهل عكسه.
لأي قيمة k ∈ K ، وبدون وجود باب خلفي t _k ، ولأي خوارزمية PPT، فإن احتمال عكس f _k بشكل صحيح (أي، بمعلومية f _k ( x )، إيجاد صورة عكسية x' بحيث f _k ( x' ) = f _k ( x )) ضئيل للغاية. ^{[ 3 ]}^{[ 4 ]}^{[ 5 ]}

إذا كانت كل دالة في المجموعة أعلاه عبارة عن تبديل أحادي الاتجاه، فإن المجموعة تسمى أيضًا تبديل الباب الخلفي . ^{[ 6 ]}

أمثلة

في المثالين التاليين، نفترض دائمًا أنه من الصعب تحليل عدد مركب كبير (انظر تحليل الأعداد الصحيحة ).

افتراض RSA

في هذا المثال، العكس $d$ ل $e$ modulo $\phi (n)$ ( دالة أويلر للطرف العلوي لـ $n$ ) هو باب المصيدة:

f(x)=x^{e}\mod n.

إذا كان تحليل $n=pq$ إذا عُرف ذلك، فـ $\phi (n)=(p-1)(q-1)$ يمكن حساب ذلك. وبهذا يمكن حساب العكس $d$ ل $e$ يمكن حسابها $d=e^{-1}\mod {\phi (n)}$ ثم يُعطى $y=f(x)$ ، يمكننا أن نجد $x=y^{d}\mod n=x^{ed}\mod n=x\mod n$ وتستند صلابته إلى فرضية RSA. ^{[ 7 ]}

افتراض رابين للبقايا التربيعية

يترك $n$ ليكن عددًا مركبًا كبيرًا بحيث $n=pq$ ، أين $p$ و $q$ هي أعداد أولية كبيرة بحيث $p\equiv 3{\pmod {4}},q\equiv 3{\pmod {4}}$ وظلت سرية حتى بالنسبة للخصم. تكمن المشكلة في حساب $z$ منح $a$ بحيث $a\equiv z^{2}{\pmod {n}}$ الباب المصيدة هو تحليل إلى عوامل $n$ باستخدام الباب المصيدة، يمكن التعبير عن حلول z على النحو التالي: $cx+dy,cx-dy,-cx+dy,-cx-dy$ ، أين $a\equiv x^{2}{\pmod {p}},a\equiv y^{2}{\pmod {q}},c\equiv 1{\pmod {p}},c\equiv 0{\pmod {q}},d\equiv 0{\pmod {p}},d\equiv 1{\pmod {q}}$ راجع نظرية الباقي الصينية لمزيد من التفاصيل. لاحظ أنه عند إعطاء أعداد أولية $p$ و $q$ ، يمكننا أن نجد $x\equiv a^{\frac {p+1}{4}}{\pmod {p}}$ و $y\equiv a^{\frac {q+1}{4}}{\pmod {q}}$ الشروط هنا $p\equiv 3{\pmod {4}}$ و $q\equiv 3{\pmod {4}}$ ضمان أن الحلول $x$ و $y$ يمكن تعريفها بشكل جيد. ^{[ 8 ]}

انظر أيضاً

وظيفة أحادية الاتجاه

ملحوظات

↑ أوستروفسكي، الصفحات 6-9
↑ بيلار، م. (يونيو 1998). "دوال الباب الخلفي متعددة إلى واحد وعلاقتها بأنظمة التشفير بالمفتاح العام". التطورات في علم التشفير - CRYPTO '98 . سلسلة محاضرات في علوم الحاسوب. المجلد 1462. الصفحات 283-298 . doi : 10.1007/bfb0055735 . ISBN 978-3-540-64892-5. S2CID 215825522 .
↑ ملاحظات باس، التعريف 56.1
↑ ملاحظات محاضرة غولدواسير، التعريف 2.16
↑ أوستروفسكي، الصفحات 6-10، التعريف 11
↑ ملاحظات باس، التعريف 56.1؛ تعريف دوديس 7، المحاضرة 1.
↑ ملاحظات محاضرة غولدواسير، 2.3.2؛ ملاحظات ليندل، ص. 17، مثال 1.
↑ ملاحظات محاضرة غولدواسير، 2.3.4.

مراجع

ديفي، دبليو .؛ هيلمان، إم. (1976)، "اتجاهات جديدة في علم التشفير" (ملف PDF) ، معاملات IEEE في نظرية المعلومات ، 22 (6): 644-654 ، CiteSeerX 10.1.1.37.9720 ، doi : 10.1109/TIT.1976.1055638
باس، رافائيل، دورة في علم التشفير (ملف PDF) ، تم الاطلاع عليه بتاريخ 27 نوفمبر 2015
جولدواسير، شافي، ملاحظات محاضرات في علم التشفير (ملف PDF) ، تم الاطلاع عليه بتاريخ 25 نوفمبر 2015
أوستروفسكي، رافائيل، أسس علم التشفير (ملف PDF) ، تم الاطلاع عليه بتاريخ 27 نوفمبر 2015
دوديس، يفغيني، مقدمة في علم التشفير، ملاحظات المحاضرات (خريف 2008) ، تم الاطلاع عليه في 17 ديسمبر 2015
ليندل، يهودا، أسس علم التشفير (ملف PDF) ، تم الاطلاع عليه بتاريخ 17 ديسمبر 2015

[1] أوستروفسكي، الصفحات 6-9

[2] بيلار، م. (يونيو 1998). "دوال الباب الخلفي متعددة إلى واحد وعلاقتها بأنظمة التشفير بالمفتاح العام". التطورات في علم التشفير - CRYPTO '98 . سلسلة محاضرات في علوم الحاسوب. المجلد 1462. الصفحات 283-298 . doi : 10.1007/bfb0055735 . ISBN 978-3-540-64892-5. S2CID 215825522 .

[3] ملاحظات باس، التعريف 56.1

[4] ملاحظات محاضرة غولدواسير، التعريف 2.16

[5] أوستروفسكي، الصفحات 6-10، التعريف 11

[6] ملاحظات باس، التعريف 56.1؛ تعريف دوديس 7، المحاضرة 1.

[7] ملاحظات محاضرة غولدواسير، 2.3.2؛ ملاحظات ليندل، ص. 17، مثال 1.

[8] ملاحظات محاضرة غولدواسير، 2.3.4.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]