👩🏼‍🎤 🍵 🙆🏿 مشكلة حقيبة الظهر في التشفير 🎚️ 🐘 🤛🏿

مشكلة الحقيبة (مشكلة حقيبة الظهر) في التشفير هي المشكلة التي على أساسها طور مصممو التشفير الأمريكيون رالف ميركل ومارتن هيلمان أول خوارزمية تشفير المفتاح العام.

كذلك في البرنامج

صياغة مشكلة الحقيبة (+ لماذا حقيبة الظهر؟)
تحديات سهلة وصعبة
أمثلة على
التاريخ

ما هو تشفير المفتاح العام؟

, , «», .

. , , , .

: , .

, - !

استخدمت أول خوارزمية المفتاح العام العام خوارزمية الحقيبة.

بناءً على تعريف أنظمة المفاتيح العامة ، يلزم وجود مفتاحين لتشفير (وفك تشفير) الرسالة بنجاح. يعرف المستلم "القانوني" للرسالة المفتاح السري

А

بينما يمتلك المرسل مفتاحًا عامًا آخر

B

$B$ ...

ماذا تفعل إذا أصبح المفتاح العمومي معروفًا للمهاجم؟

هناك إجابة: يجب الحصول على المفتاح العمومي من المفتاح السري باستخدام تحويل ( وظيفة أحادية الاتجاه )

f

$f$ بالخاصيتين التاليتين:

$B = f(A)$ بمعرفة A ، من السهل حساب الوظيفة نفسها

$A = f^{-1} (B)$ ، ومن الصعب حساب الدالة العكسية

ما هو "سهل" و "صعب"؟

.

«» , . ..

n

$n$ , —

t \propto n^{a}

$t \propto n^a$ ,

a

$a$ — . , .

«» . , , .

..

n

$n$ ,

t \propto 2 n

$t \propto 2n$ , , .

تمت صياغة مشكلة الحقيبة على النحو التالي

المجموعة (ناقلات حقيبة الظهر)

A = (a_{1}, . . ., a_{n})

$A = (a_1, ... , a_n)$ هي مجموعة مرتبة من

n

$n$ (

n > 2),

$n > 2),$ أعداد طبيعية مميزة

a_{i}

$a_i$ ... يجب ألا يكون هناك رقم

k

$k$ - كلي وإيجابي. المهمة هي العثور على مثل هذه المجموعة

a_{i}

$a_i$ بحيث في المجموع يعطون بالضبط

k

$k$ ...

في النسخة الأكثر شهرة من مشكلة الحقيبة على الظهر ، يلزم معرفة ما إذا كان زوج معين لديه

(A, k)

$(A , k)$ القرار. في المتغير المستخدم في التشفير ، تحتاج إلى هذا الإدخال

(A, k)

$(A , k)$ بناء حل مع العلم أن مثل هذا الحل موجود. كلا الخيارين NP-Complete.

تشبيه حقيبة الظهر

في أبسط الحالات

k

$k$ يشير إلى حجم (سعة) حقيبة الظهر ، وكل رقم من الأرقام

a_{i}

$a_i$ يشير إلى حجم (وزن) عنصر يمكن تعبئته في حقيبة ظهر. تتمثل المهمة في العثور على مثل هذه المجموعة من العناصر بحيث

تمتلئ حقيبة الظهر بالكامل.

أي تخيل أن لديك مجموعة من الأوزان 1 و 6 و 8 و 15 و 24 ، فأنت بحاجة إلى حزم حقيبة ظهر بوزن 30.

من حيث المبدأ ، يمكن دائمًا العثور على حل من خلال البحث الشامل لمجموعات فرعية

А

والتحقق من المبالغ

k

$k$ ... في حالتنا ، هذا يعني القوة الغاشمة

2^{5} = 32

$2^5 = 32$ مجموعات فرعية (بما في ذلك المجموعة الفارغة). هذا ممكن تماما

ولكن ماذا لو كان هناك عدة مئات من الأرقام $a_i$ ؟

في مثالنا ، n = 5 ، حتى لا يتم تعقيد العرض. في الظروف الحقيقية ، سيكون المثال ، على سبيل المثال ، 300

a_{i} - х

$a_i-$ ... خلاصة القول هي أن الخوارزميات غير معروفة ولها تعقيد أقل بكثير مقارنة بالبحث الشامل. البحث بين

2^{300}

$2^{300}$ لا يمكن معالجة مجموعات فرعية. في الواقع ، تُعرف مشكلة الحقيبة على الظهر باسم NP-complete ... وتعتبر مشاكل NP الكاملة صعبة الحساب.

هل الوظيفة تلبي المتطلبات المحددة؟

نحدد الوظيفة

f (x)

$f(x)$ بالطريقة الآتية. أي رقم

0 \leq x \leq 2 n - 1

$0 ≤ x ≤ 2n − 1$ يمكن الحصول عليها من خلال تمثيل ثنائي من

n

$n$ بت ، حيث يتم إضافة الأصفار البادئة إذا لزم الأمر. الآن دعنا نحدد

f (x)

$f(x)$ كرقم تم الحصول عليها من

A

$A$ تلخيص كل هذا

a_{i}

$a_i$ أن البت المقابل في التدوين الثنائي

x

$x$ يساوي 1.

أي

f (1) = f (0 . . . 001) = a_{n}

$f(1) = f(0 . . . 001) = a_n$

f (2) = f (0 . . . 010) = a_{n - 1}

$f(2) = f(0 . . . 010) = a_{n−1}$

f (3) = f (0 . . . 011) = a_{n - 1} + a_{n}

$f(3) = f(0 . . . 011) = a_{n−1} + a_n$

. . .

$...$

وظيفة

f (х)

$f( )$ تم تحديده

n -

$n-$ جلس

A

$A$ ... من الواضح ، إذا كنا قادرين على الحساب

x

$x$ من

f (x)

$f(x)$ ، ثم في نفس الوقت تقريبًا سيتم حل مشكلة حقيبة الظهر:

x

$x$ يتم حساب تمثيلها الثنائي على الفور ، والذي بدوره يعطي مكونات المجموعة

A

$A$ المدرجة في المجموع ل

f (x)

$f(x)$ ... من ناحية أخرى ، الحساب

f (x)

$f(x)$ من

x

$x$ خفيف الوزن. نظرًا لأن مشكلة حقيبة الظهر مكتملة NP ،

f (x)

$f(x)$ هو مرشح جيد لوظيفة أحادية الاتجاه. بالطبع ، يجب على المرء أن يطالب بذلك $n$ كان كبيرًا بما يكفي ، على سبيل المثال لا أقل $200$ ...

التشفير

نص عادي

(. plain text) — , , . ( ).

يمكنك التشفير بطريقتين:

يتم الحصول على تشفير الرسالة عن طريق رفع عناصر متجه الحقيبة هذا إلى قوة البتات المقابلة للرسالة المشفرة ثم ضرب جميع النتائج ، أي إذا $A = (2,3,5)$ والرسالة $(100)$ ، ثم سيكون التشفير هو الرقم $2^1*3^0*5^0=2$ ... هذه طريقة مضاعفة .
يتم الحصول على تشفير الرسالة بضرب عناصر متجه الحقيبة هذا في البتات المقابلة للرسالة المشفرة ثم تلخيص جميع النتائج ، أي إذا $A = (2,3,5)$ والرسالة $(100)$ ، ثم سيكون التشفير هو الرقم $2^ *1+3^ *0+5^ *0= 2$ ... هذه الطريقة تسمى المضافة .

مثال

لتشفير نص عادي في التمثيل الثنائي ، يتم تقسيمه إلى كتل من الطول

n

$n$ (على سبيل المثال ، يمكنك تمثيل الوزن 30 مع النظام الثنائي 11110). يُعتقد أن المرء يشير إلى وجود عنصر في حقيبة الظهر ، ويشير الصفر إلى عدم وجوده.

يوفر تشفير حقيبة الظهر طريقة جيدة لإنشاء مفاتيح عامة وخاصة ، حيث يكون المفتاح الخاص سهل الاستخدام ويصعب اكتشاف المفتاح العام.

لذلك ، يمكننا إنشاء نظام حيث: المشكلة "الصعبة" هي

المفتاح العمومي ، لأن يمكن استخدامه للتشفير بسهولة ولا يمكن فك تشفيره.

مفتاح خاص - ستكون المشكلة "السهلة" بمثابة باستخدامه ، يمكنك بسهولة فك تشفير الرسالة. بدون مفتاح خاص ، يجب عليك حل مشكلة حقيبة الظهر "الصعبة".

مشكلة "سهلة"

سوبر تزايد ناقلات حقيبة الظهر

A = (a_{1}, . . ., a_{n})

$A=(a_{1},...,a_{n})$ ,

Σ_{i = 1}^{j - 1} a_{i} < a_{j}

$Σ_{i=1}^{j-1} a_{i} < a_{j}$

j = 2, . . ., n

$j=2,...,n$ , . .

بالنسبة للناقلات فائقة النمو ، يمكن حل مشكلة حقيبة الظهر بسهولة. أولئك. حقيبة الظهر سهلة التجميع.

لنأخذ مثالا:

الخوارزمية

.

, , . , .
.
(1)-(2) .

, .

"مشكلة صعبة

من الصعب جدًا فك شفرة مشكلة حقيبة الظهر غير الكبيرة الحجم .

تم إنشاء خوارزمية واحدة ، والتي تستخدم حقيبة ظهر ذات مفتاح خاص كبير الحجم وحقيبة ظهر ذات مفتاح عام غير كبير الحجم ، بواسطة Merkle و Hellman.

لقد فعلوا ذلك عن طريق أخذ مهمة حقيبة الظهر كبيرة الحجم وتحويلها إلى مهمة غير كبيرة الحجم.

(ابتكر ميركل وهيلمان ، باستخدام الحساب المعياري ، طريقة لتحويل حقيبة الظهر "الخفيفة" إلى حقيبة "صلبة")

إنشاء مفتاح عمومي

عدة مفاهيم مهمة

$(x, mod m)$ $x$ $m$ ,

$x$ — , $m > 1$ , [x/m] — ,
$x = (x, m o d m) + [x / m] * m$
$x = (x, mod m) + [x/m]*m$

$A$ , $m > max A$ $t < m$ , $(t, m) = 1$ .

$B = (b_1, . . . , b_n)$ , $b_i = (ta_i, modm)$ , $i = 1, . . . , n$ , , B A m t , , $(m, t)$ .

$(t, m) = 1$

$t^{−1} = u$ , ,

$t u \equiv 1 (m o d m)$
$tu ≡ 1 (mod m)$

$1 ≤ u < m$ . , $A$ $B$

$m, u$ .

$m > max A$

$m > Σ_{i=1}^{n} a_{i}$ , , $B$ $A$ $m, t$ .

— , , , .

منشئ نظام التشفير يختار مثل هذا النظام

A, t, m, B

$A, t, m, B$ هذا المتجه

A

$A$ ينمو بشكل كبير ، و

B

$B$ يأتي من

A

$A$ ضرب معياري قوي فيما يتعلق

m, t

$m, t$ ... المتجه

B

$B$ تم توسيعه كمفتاح تشفير وكتل ثنائية للطول

n

$n$ يتم إرسالها إلى المصمم كأرقام

β

$β$ تم الحصول عليها باستخدام المتجه

B

$B$ ...

يجب أن يحل جهاز اعتراض الرسائل مشكلة الحقيبة

(B, β)

$(B, β)$ ... منشئ نظام التشفير يحسب

α = (u β, m o d m)

$α = (uβ, modm)$

ويحل مشكلة دخول حقيبة الظهر

(A, α)

$(A, α)$ ... لماذا

يظهر كل هذا في اللمة التالية.

ليما . دعونا نتظاهر بذلك

A = (a_{1}, . . ., a_{n})

$A = (a_1, . . . , a_n)$ ناقلات فائقة النمو وناقلات

B

$B$ مستمدة من

A

$A$ ضرب معياري قوي فيما يتعلق

m, t

$m, t$ ... افترض كذلك

u \equiv t^{- 1} (m o d m)

$u ≡ t^{−1} (mod m)$ و

β

$β$ - عدد طبيعي تعسفي و

α = (u β, m o d m)

$α = (uβ,modm)$ ... ثم العبارات التالية صحيحة.

(ط) مشكلة الحقيبة

(A, α)

$(A, α)$ قابل للحل في الوقت الخطي. إذا كان هناك حل ، فهو فريد من نوعه.

(2) مشكلة الحقيبة

(B, β)

$(B, β)$ لديه حل واحد على الأكثر.

(3) إذا كان هناك حل للدخول

(B, β)

$(B, β)$ ثم يطابق حل الدخول الوحيد

(A, α)

$(A, α)$ ...

برهان (ص 104)

مثال

تأمل في تسلسل فائق النمو ؛ على سبيل المثال ، {1 ، 2 ، 4 ، 10 ، 20 ، 40}. يجب أن يكون المعامل أكبر من مجموع كل الأرقام في التسلسل ، على سبيل المثال 110. يجب ألا يكون للمضاعف قواسم مشتركة مع المعامل. لذلك دعونا نختار 31.

لذلك ، حسبنا المفتاح العمومي: {31 ، 62 ، 14 ، 90 ، 70 ، 30} والمفتاح الخاص - {1 ، 2 ، 4 ، 10 ، 20.40}.

لنحاول الآن إرسال تسلسل ثنائي: 100100111100101110

بعض فوائد المفاتيح العامة

عند استخدام نظام تشفير بالمفتاح العام ، لا يلتقي الطرفان ، وقد لا يعرف كل منهما الآخر ويستخدم أي نوع من الاتصالات.

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

التاريخ

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

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

يعتقد بعض الناس أنه في يوم من الأيام يمكن اختراع خوارزمية متعددة الحدود لحل مشاكل العوامل اللوغاريتمية المنفصلة ، بينما لا تزال مشكلة الحقيبة على الظهر مكتملة NP.

هناك العديد من "BUTs" هنا.

أولاً ، يعتمد اكتمال NP على تحليل أسوأ الحالات ؛ ثانيًا ، يعد اكتمال NP سمة لمشكلة عامة ، وليس حالة معينة. هذا يعني أنه إذا أخذنا في الاعتبار متوسط التعقيد ، يمكن أن تكون مشكلة حقيبة الظهر سهلة.

تم إعداد المادة على أساس هذه الأدبيات:

(1) أ. سالوما. تشفير المفتاح العام. - سبرينغر فيرلاغ ، 1990. - ص. 75-82 ، ص 101-111

(2)مين كين لاي. أنظمة التشفير على الحقيبة : الماضي والمستقبل - جامعة كاليفورنيا ، 2001

(3) باوكانغ وانغ ، تشيان هونغ وو ، يوبو هو. مخطط تشفير احتمالي قائم على الحقيبة. 2007

(4) - (5)

مشكلة حقيبة الظهر في التشفير