خوارزمية متناظرة للأعداد الصحيحة

Question

أحتاج إلى خوارزمية يمكنها القيام برسم خرائط فردي (أي أي تصادم) من عدد صحيح موقّع 32 بت على عدد صحيح موقّع 32 بت.

قلقي الحقيقي هو إنتروبيا كافية بحيث يبدو أن إخراج الوظيفة عشوائيًا. في الأساس ، أبحث عن تشفير مشابه لـ Xor Cipher ، لكن يمكن أن يولد مخرجات أكثر تعسفيًا. الأمن ليس شاغلي الحقيقي ، على الرغم من أن الغموض هو.

تحرير لغرض التوضيح:

1. الخوارزمية يجب كن متماثلًا ، حتى أتمكن من عكس العملية بدون keypair.
2. الخوارزمية يجب كن محيرا ، يجب أن يولد كل رقم إدخال 32 بت 32 بت فريدة من نوعها.
3. يجب أن يكون إخراج الوظيفة غامضًا بدرجة كافية ، فإن إضافة واحد فقط إلى الإدخال يجب أن يؤدي إلى تأثير كبير على الإخراج.

مثال النتيجة المتوقعة:

F (100) = 98456
F (101) = -758
F (102) = 10875498
F (103) = 986541
F (104) = 945451245
F (105) = -488554

تمامًا مثل MD5 ، قد يغير تغيير شيء واحد الكثير من الأشياء.

أنا أبحث عن وظيفة رياضية ، لذا فإن تعيين الأعداد الصحيحة يدويًا ليس حلاً بالنسبة لي. بالنسبة لأولئك الذين يسألون ، فإن سرعة الخوارزمية ليست مهمة للغاية.

Answer 1

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

للحصول على امتداد لهذه الفكرة إلى نطاقات غير الطاقة من 2 ، راجع مشاركتي التباديب الآمن مع أصفاف الكتلة.

معالجة مخاوفك المحددة:

1. الخوارزمية متماثلة بالفعل. لست متأكدًا مما تقصده بـ "عكس العملية بدون keypair". إذا كنت لا ترغب في استخدام مفتاح ، فقم بإنشاء رمز Hards الذي تم إنشاؤه بشكل عشوائي واعتبره جزءًا من الخوارزمية.
2. نعم - بحكم التعريف ، تشفر الكتفين.
3. نعم. لن يكون تشفيرًا جيدًا إذا لم يكن الأمر كذلك.

Answer 2

سأحاول شرح حلي لهذا على مثال أبسط بكثير ، والذي يمكن بعد ذلك تمديده بسهولة لحلك الكبير.

قل لدي رقم 4 بت. هناك 16 قيمة متميزة. انظر إليه كما لو كان مكعبًا رباعي الأبعاد:
_{(مصدر: ams.org)}
.

يمثل كل قمة رأس أحد هذه الأرقام ، ويمثل كل بتة بعدًا واحدًا. لذا فإن xyzw الأساسي ، حيث يمكن أن يكون لكل من الأبعاد قيم فقط 0 أو 1. تخيل الآن أنك تستخدم أ ترتيب مختلف من الأبعاد. على سبيل المثال Xzyw. كل من القمم غيرت الآن رقمها!

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

Answer 3

تمنحك الورقة التالية 4 أو 5 أمثلة رسم الخرائط ، مما يتيح لك وظائف بدلاً من بناء مجموعات تم تعيينها: www.cs.auckland.ac.nz/~john-rugis/pdf/bijectivemapping.pdf

Answer 4

بصرف النظر عن توليد طاولات بحث عشوائية ، يمكنك استخدام مجموعة من الوظائف:

• xor
• التقليب المتماثل (على سبيل المثال Shift 16 بت ، أو قلوب من 0-31 إلى 31-0 ، أو قلب 0-3 إلى 3-0 ، 4-7 إلى 7-4 ، ...)
• أكثر؟

Answer 5

إذا كان هدفك هو ببساطة الحصول على تقليب عشوائي على ما يبدو لأعداد أ بقسوة الحجم المحدد ، ثم هناك طريقة أخرى ممكنة: قلل من مجموعة الأرقام إلى عدد أولي.

ثم يمكنك استخدام رسم خرائط للنموذج

f (i) = (i * a + b) ٪ p

وإذا كان P بالفعل برايم ، فسيكون هذا إحياءًا لكل A! = 0 وكل B. سيبدو عشوائيًا إلى حد ما لأكبر A و B.

على سبيل المثال ، في حالتي التي عثرت عليها في هذا السؤال ، استخدمت 1073741789 كرئيس رئيسي لنطاق الأرقام الأصغر من 1 << 30. وهذا يجعلني أفقد 35 رقمًا فقط ، وهو أمر جيد في حالتي.

تشفير بلدي بعد ذلك

((n + 173741789) * 507371178) % 1073741789

وفك التشفير

(n * 233233408 + 1073741789 - 173741789) % 1073741789

لاحظ أن 507371178 * 233233408 ٪ 1073741789 == 1 ، لذلك فإن هذين الرقمين يعكسان حقل الأرقام MODULO 1073741789 (يمكنك معرفة الأرقام العكسية في هذه الحقول مع الخوارزمية الإقليدية الممتدة).

لقد اخترت A و B بشكل تعسفي إلى حد ما ، لقد تأكدت فقط من أنهما تقريبًا نصف حجم p.

Answer 6

هل يمكنك استخدام جدول بحث تم إنشاؤه عشوائيًا؟ طالما أن الأرقام العشوائية في الجدول فريدة من نوعها ، ستحصل على رسم خرائط للتخليق. انها ليست متماثلة ، رغم ذلك.

من المحتمل ألا يكون طاولة البحث 16 جيجابايت لجميع قيم 32 بت من العمليات ، ولكن يمكنك استخدام طاولتين منفصلتين لاستثناء 16 بت للكلمة العالية والكلمة المنخفضة.

ملاحظة: أعتقد أنه يمكنك إنشاء جدول بحث متماثل ، إذا كان ذلك مهمًا. ستبدأ الخوارزمية مع LUT فارغة:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

اختر العنصر الأول ، قم بتعيينه رسم خرائط عشوائي. لجعل التعيين متماثلًا ، قم بتعيين العكسي أيضًا:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

اختر الرقم التالي ، مرة أخرى ، قم بتعيين تعيين عشوائي ، ولكن اختر رقمًا لم يتم تعيينه بعد. (أي في هذه الحالة ، لا تختار 1 أو 3). كرر حتى يكتمل lut. هذا يجب أن يولد رسم خرائط متماثل عشوائي.

Answer 7

خذ رقمًا ، يتضاعف بمقدار 9 ، أرقام عكسية ، يقسم على 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

يجب أن تكون غامضة بما فيه الكفاية !!

تحرير: إنه ليس مستكومًا لعدد صحيح 0

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

يمكنك دائمًا إضافة قاعدة محددة مثل: خذ رقمًا ، وقسّمها على 10 × مرات ، وتضاعف 9 ، أرقام عكسية ، تقسيم على 9 ، مضاعفات على 10^x.

وهكذا

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00T يعمل!

تحرير 2: لمزيد من الغموض ، يمكنك إضافة رقم تعسفي ، والفروع في النهاية.

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

Answer 8

إليكم فكرتي البسيطة: يمكنك التنقل حول أجزاء الرقم ، كما اقترح بيترك ، ولكن يمكنك الحصول على تقليب مختلف لكل رقم ، ولا تزال قادرة على فك رموزه.

يذهب الشفرات مثل هذا: تعامل مع رقم الإدخال كمجموعة من البتات I[0..31], ، والإخراج كما O[0..31]. إعداد صفيف K[0..63] من 64 أرقام تم إنشاؤها عشوائيا. سيكون هذا مفتاحك. خذ الجزء من رقم الإدخال من الموضع الذي يحدده الرقم العشوائي الأول (I[K[0] mod 32]) ووضعها في بداية النتيجة (O[0]). الآن لتقرير أي جزء يجب وضعه في O[1], ، استخدم بت المستخدمة مسبقًا. إذا كان 0 ، استخدم k [1] لإنشاء موضع في I من ذلك الذي يجب أن يأخذ ، هو 1 ، استخدم K [2] (مما يعني ببساطة تخطي رقم عشوائي واحد).

الآن لن يعمل هذا بشكل جيد ، حيث قد تأخذ نفس الشيء مرتين. من أجل تجنب ذلك ، قم بإعادة ترقيم البتات بعد كل تكرار ، مع حذف البتات المستخدمة. لتوليد الموقف الذي يجب اتخاذه O[1] استعمال I[K[p] mod 31], ، حيث p هو 1 أو 2 ، اعتمادا على البت O[0], ، حيث يوجد 31 بتات ، ترقيم من 0 إلى 30.

لتوضيح ذلك ، سأقدم مثالاً:

لدينا رقم 4 بت ، و 8 أرقام عشوائية: 25 ، 5 ، 28 ، 19 ، 14 ، 20 ، 0 ، 18.

I: 0111    O: ____
    _

25 Mod 4 = 1 ، لذلك سنأخذ بت من هو موقعه 1 (العد من 0)

I: 0_11    O: 1___
     _

لقد أخذنا للتو قليلاً من القيمة 1 ، لذلك نتخطى رقمًا عشوائيًا واحدًا ونستخدم 28. هناك 3 بتات ، لذا لحساب الموضع ، نأخذ 28 mod 3 = 1. نأخذ الأول (العد من 0) البتات المتبقية:

I: 0__1    O: 11__
   _

مرة أخرى ، نتخطى رقمًا واحدًا ، ونأخذ 14. 14 mod 2 = 0 ، لذلك نأخذ البت 0:

I: ___1    O: 110_
      _

الآن لا يهم ، لكن الشيء السابق كان 0 ، لذلك نأخذ 20. 20 mod 1 = 0:

I: ____    O: 1101

وهذا هو.

من السهل فك رموز هذا الرقم ، على المرء أن يفعل نفس الأشياء. الموضع الذي يجب عنده وضع الجزء الأول من الكود معروف من المفتاح ، يتم تحديد المواضع التالية بواسطة بتات تم إدراجها مسبقًا.

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

Answer 9

إذا كنت لا ترغب في استخدام خوارزميات التشفير المناسبة (ربما لأسباب الأداء والتعقيد) ، يمكنك بدلاً من ذلك استخدام تشفير أبسط مثل Vigenère cipher. تم وصف هذا التشفير بالفعل على أنه لو شيفري indéchiffrable (الفرنسية لـ "الشفرة غير القابلة للكسر").

فيما يلي تطبيق C# بسيط يغير القيم بناءً على قيمة المفتاح المقابلة:

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

لا تنشئ هذه الخوارزمية تحولًا كبيرًا في الإخراج عند تغيير الإدخال قليلاً. ومع ذلك ، يمكنك استخدام عملية تخطيفية أخرى بدلاً من الإضافة لتحقيق ذلك.

Answer 10

ارسم دائرة كبيرة على ورقة كبيرة. اكتب جميع الأعداد الصحيحة من 0 إلى Maxint في اتجاه عقارب الساعة من أعلى الدائرة ، متباعدة بالتساوي. اكتب جميع الأعداد الصحيحة من 0 إلى Minint عكس اتجاه عقارب الساعة ، متباعدة بالتساوي مرة أخرى. لاحظ أن Minint يقع بجوار Maxint في أسفل الدائرة. الآن قم بعمل مكررة من هذا الرقم على جانبي قطعة من البطاقة القاسية. قم بتثبيت البطاقة القاسية إلى الدائرة من خلال مراكز الاثنين. اختر زاوية الدوران ، أي زاوية تريدها. الآن لديك رسم خرائط 1-1 يلبي بعض متطلباتك ، ولكن ربما لا تكون غامضة بما فيه الكفاية. قم بإلغاء وضع البطاقة ، وقلبها حول قطر ، أي قطر. كرر هذه الخطوات (بأي ترتيب) حتى يكون لديك أعراض راسخة.

إذا كنت تتابع عن كثب ، فلا ينبغي أن يكون من الصعب برمجة ذلك بلغتك المفضلة.

للتوضيح بعد التعليق: إذا قمت فقط بتدوير البطاقة مقابل الورقة ، فإن الطريقة بسيطة كما تشكو. ومع ذلك ، عندما تقلب البطاقة فوق التعيين لا تعادل (x+m) mod MAXINT لأي m. على سبيل المثال ، إذا تركت البطاقة غير مقاس وقلبها حول القطر من خلال 0 (وهو في الجزء العلوي من وجه الساعة) ، فسيتم تعيين 1 إلى -1 و 2 إلى -2 وما إلى ذلك. (x+m) mod MAXINT يتوافق مع دورات البطاقة فقط.

Answer 11

قم بتقسيم الرقم في اثنين (16 أجمل البتات و 16 بت أقل أهمية) والنظر في البتات في النتائج الـ 16 بت كبطاقات في طابقين. امزج الطوابق التي تجبر المرء على الآخر.

لذلك إذا كان رقمك الأولي b31,b30,...,b1,b0 ينتهي بك المطاف مع b15,b31,b14,b30,...,b1,b17,b0,b16. إنه سريع وسريع للتنفيذ ، كما هو عكسي.

إذا نظرت إلى التمثيل العشري للنتائج ، فإن السلسلة تبدو غامضة إلى حد ما.

يمكنك خريطة 0 -> maxvalue و maxvalue -> 0 لتجنب التعيين على أنفسهم.