חילוץ מפתח XOR מתוך מספרים ממויינים

[yossiz]

תגובה: תרגיל מתמטי של הסתרת מזהה רץ

בהמשך לנושא הנ"ל,

@dovid אמר בתרגיל מתמטי של הסתרת מזהה רץ:

הנה XOR למספרים עוקבים על מספר רנדומלי:
159866
159865
159864
159871
159870
159869
159868
159859
159858
159857

@dovid אמר בתרגיל מתמטי של הסתרת מזהה רץ:

אגב הרשימה של הXOR הינה אתגר הרבה יותר קל והוא לא הדליק פה מישהו ככל הנראה.

אדרבה, זה הדליק אותי מאוד,
(אמנם רק ביום שישי התחלתי לחשוב על זה ברצינות)

אפשר לחלק את האתגר לשנים:

• חילוץ המפתח מתוך מספרים עוקבים
• מתוך מספרים ממוינים, אבל לא בהכרח עוקבים

(עוד שאלה, האם אפשר לזהות אם המספרים עוקבים או לא? ספויילר... כן, בקלות)

הנה פתרון לחלק הראשון (מספרים עוקבים) ב-JS:

function makeRand (max) {
  return Math.floor(Math.random() * max)
}

function makeRange (start, length) {
  const ret = []
  for (i = 0; i < length; i++) {
    ret.push(start + i)
  }
  return ret;
}

function makeBitmask(width) {
  return width && -1 >>> 32 - width;
}

const KEY = makeRand(1000)

const nums = makeRange(makeRand(1000), 60)

// console.log('Numbers:', nums)

function extractXORKeySeq (numList) {
  let bestDiff, bestIndex
  bestDiff = bestIndex = -1
   
  for (let i = 1; i < numList.length; i++) {
    const diff = numList[i] ^ numList[i-1]
    if (diff & (diff + 1)) {
      throw new Error('Numbers are not sequential!')
    }
    if (diff > bestDiff) {
      bestDiff = diff
      bestIndex = i
    }
  }
   
  const previous = numList[bestIndex - 1]
  const extractLen = bestDiff.toString(2).length
  const keyBits = bestDiff ^ (previous ^ (1 << (extractLen - 1))) & makeBitmask(extractLen)

  return [extractLen, keyBits]
}

const [len, bits] = extractXORKeySeq(nums.map(i => i ^ KEY))

console.log(`Extracted last ${len} bits of the key: ${bits.toString(2).padStart(len, '0')}`)
console.log(`Real key is: ${KEY} (${KEY.toString(2)})`)
// console.log(`numList after decryption: ${nums.map(i => i ^ KEY).map(i => i ^ bits)}`)
console.assert(KEY.toString(2).padStart(32, '0').endsWith(bits.toString(2).padStart(len, '0')))

נ.ב. אשאיר פה את הקוד בלי הסבר לבינתיים למי שירצה להתעמק לבד...
מחר או מחרתיים יבוא ההסבר בל"נ
לענ"ד יותר קל למצוא את הפתרון באמצעות מחשבה מאשר לנסות לעקוב אחרי הקוד הזה...

עריכה: יש חסרון בקוד. אני מחלץ פחות ביטים מהמקסימום התיאורטי. אתקן בהזדמנות

עדכון: הקוד תוקן סופית. זה אמור להיות מושלם עכשיו

[קומפיונט]

@yossiz אנחנו מצפים בכיליון עיניים להסבר שלך.

[חגי]

@yossiz
אני שם לב שאם המפתח גדול בהרבה מהגודל של המספרים העוקבים, הXOR הכי גדול שאתה יכול להגיע אליו מכיל פחות ביטים מהמפתח עצמו, מה ששוב עושה שאי אפשר לגלות את המספר המקורי.
מאחר ומדובר במספרים עוקבים שמייצגים מספר כניסה, אפשר להניח שהם לא יעברו את ה100,000,000 בבטחה, לא? כמו כן ניתן להניח שלא יהיו להם תוצאות של יותר מ-10,000 כניסות עוקבות.
בוא נעמיד את זה לבדיקה:

const KEY = 200_000_000

const nums = makeRange(100_000_000, 10_000)
 
const [len, bits] = extractXORKeySeq(nums.map(i => i ^ KEY))
 
console.log(`Extracted last ${len} bits of the key: ${bits.toString(2).padStart(len, '0')}`)
console.log(`Real key is: ${KEY.toString(2)}`)
console.assert(KEY.toString(2).padStart(32, '0').endsWith(bits.toString(2).padStart(len, '0')))  

והתוצאה:

Extracted last 17 bits of the key: 11100001000000000
Real key is: 1011111010111100001000000000

(זה לא יפה מצידי למצוא איפה הקוד שלך נכשל, בעוד שאני בכלל לא הצלחתי להגיע לשום פיתרון)

[yossiz]

הסבר הקוד הנ"ל

השיטה לחלץ את המפתח בנויה על שתי ההערות הבאות:

פעולת XOR:

אפשר להסתכל על פעולת XOR בצורה כזו: בכל מקום שיש ביט 1 במפתח אנחנו מחליפים בקלט 1 ל-0 ו-0 ל-1.
יוצא ששום מידע לא הולך לאיבוד בפלט, רק ששמור בסוד בתוך המפתח באיזה ביט משמעותו של 1 הוא 1 ובאיזה מהם משמעותו 0. וכן לגבי 0 איזה מהם משמעותו 0 ואיזה מהם משמעותו 1.

מספרים בינאריים עוקבים:

אפשר ליצור רצף של מספרים עוקבים בינאריים אם נעקוב אחרי שני כללים פשוטים:

• בכל איטרציה נחליף את הערך של הביט הכי ימני
• כל ביט שערכו הופך מ-1 ל-0, גורר שינוי בביט שלשמאלו

למשל, אם נתחיל במספר 0

• איטרציה 1: נחליף את הערך של הביט הכי ימני => קיבלנו 1
• איטרציה 2: נחליף את הערך של הביט הכי ימני, יצא 0, עכשיו לפי הכלל השני זה מחייב אותנו לשנות את הביט שלשמאלו מ-0 ל-1 => קיבלנו 10
• איטרציה 3: כלל 1 => 11
• איטרציה 4: כלל 1 נותן לנו 10 כלל 2 מחייב שינוי בביט השני , קיבלנו 00 שוב כלל 2 מחייב שינוי בביט השלישי => קיבלנו 100

וכן הלאה, אם רק נעקוב אחרי שני כללים אלו ניצור תמיד את המספר הבא ברצף

יוצא מזה שאפשר לזהות מספרים שאינם עוקבים אם הם לא מתאימים לתבנית זו. כלומר, או שהשינויים לא מתחילים מימין, או ששינוי של ביט שמאלי יותר לא נגרר משינוי של הביט לימינו מ-1 ל-0

והנה במספרים שמוצפנים בשיטת XOR, כבר אי אפשר לדעת אם ה-1 הוא 1 או 0 אבל עדיין אפשר לדעת שמספרים אינם עוקבים לפי הכלל השני, אם נראה שינוי בביט שמאלי כאשר אין שינוי בביט שלימינו נדע שהמספרים לא עוקבים

ולפי זה נבין גם איך לזהות את הביטים של מפתח ההצפנה, אם נראה שינוי בביט כלשהו שנגרר משינוי של הביט לימינו מ-0 ל-1 במקום מ-1 ל-0 נדע שהביט לימינו משמעותו הפוך שה-1 הוא 0 וה-0 הוא 1 וכך אנו עולים עם ביט 1 במפתח ההצפנה

ומכאן להסבר הקוד:

הקוד מתחיל עם כמה פוקציות עזר, היחיד מביניהם שאולי דורש הסבר זה makeBitmask
התפקיד של פונקציה זו היא ליצור "מסיכה" של ביטים באורך מסויים. (נראה בהמשך למה זה שימושי). דרך אחת לעשות את זה הוא על ידי פעולת right shift על מספר שמורכב רק מביטים של 1. אז אנו לוקחים את המספר -1 שבשיטת ‎2's complement (שיטת ייצוג מספרים שלמים במעבדים) הוא מורכב מרצף של 32 (או 64) ביטים של 1., ואז אנו עושים פעולתunsigned right shift עליו כדי לדחוף את המספר הנכון של ביטים של 0 משמאל.
הקוד לקחתי מפה: https://stackoverflow.com/a/43894311

function makeRand (max) {
  return Math.floor(Math.random() * max)
}
 
function makeRange (start, length) {
  const ret = []
  for (i = 0; i < length; i++) {
    ret.push(start + i)
  }
  return ret;
}
 
function makeBitmask(width) {
  return width && -1 >>> 32 - width;
}

פה אנו יוצרים את רשימת המספרים ומפתח אקראי בין 1 - 1000

const KEY = makeRand(1000)
 
const nums = makeRange(makeRand(1000), 60)
 
// console.log('Numbers:', nums)

כאן אנו מגיעים לבשר:
שלב ראשון נרצה למצוא את המספר שבו הכי הרבה ביטים משתנים בו לעומת המספר הקודם, כי זה יאפשר לנו לגלות הכי הרבה ביטים של המפתח (יצויין, לא תמיד אפשר לגלות את כל הביטים, הקוד שלי מגלה את המקסימום האפשרי)
זה התפקיד של הלולאה.
תוך כדי כך אנו בודקים גם כן שמדובר במספרים עוקבים
הבדיקה היא על ידי XOR עם המספר הקודם.
זה נותן לנו ביט של 1 בכל מיקום שהקודם היה 0 והנוכחי 1 או הפוך, הוי אומר - כל ביט שהשתנה לעומת המספר הקודם
קיבלנו מפה של ביטים
כדי לוודא שמדובר במספר עוקב אנו צריכים לבדוק שהשינויים זורמים מימין לשמאל, זה נעשה על ידי בדיקה שהמספר מורכב מביטים של 1 בלבד (מספר כזה יש לו רק ביטים של 1 לצד ימין).
יש דרכים לבקוד את זה, אני השתמשתי בדרך קצת טריקית (חכמה ) שמובאת פה: https://www.geeksforgeeks.org/check-bits-number-set ה-method 2

function extractXORKeySeq (numList) {
  let bestDiff, bestIndex
  bestDiff = bestIndex = -1
   
  for (let i = 1; i < numList.length; i++) {
    const diff = numList[i] ^ numList[i-1]
    if (diff & (diff + 1)) {
      throw new Error('Numbers are not sequential!')
    }
    if (diff > bestDiff) {
      bestDiff = diff
      bestIndex = i
    }
  }

מקווה שעד כאן מובן,
ואם כן, הרי קיבלנו את המספר שהכי השתנה בביטים מהמספר הקודם
עכשיו אנו לוקחים את מפת הביטים ו-
א. האורך של מפת הביטים זה האורך המקסימלי של המפתח שנוכל לחלץ (אנו מקבלים את האורך על ידי הפיכה למחרוזת ומדידת האורך, בטח יש דרכים יותר חסכוניות, חכמות, טריקיות לזה...)
ב. נרצה לדעת מתוך זה איזה ביטים השתנו מ-0 ל-1 כי אלה הם הביטים שלא היו אמורים לגרור שינוי בביט שלימינם, ואם הם גררו שינוי - סימן שהם הפוכים (כלומר, ערכם 1 במפתח ה-XOR)
ג. הביט הכי שמאלי, נרצה לבדוק שהוא שינוי מ-0 ל-1 אחרת הוא היה אמור לגרור עוד שינוי בביט שלשמאלו
לשם ב וג הנ"ל אנו עושים XOR של המפה עם המספר הקודם, רק שלפני כן אנו הופכים את הביט שמקביל לביט הכי שמאלי של המפה, דוק ותשכח שזה נותן לנו את המידע
אח"כ אני "מנקים" את שאר המספר (הופכים ל-0) על ידי פעולת AND עם מסיכה שאנו יוצרים עם פונקציית העזר הנ"ל
והנה קיבלנו את התוצאה!

  const previous = numList[bestIndex - 1]
  const extractLen = bestDiff.toString(2).length
  const keyBits = bestDiff ^ (previous ^ (1 << (extractLen - 1))) & makeBitmask(extractLen)
 
  return [extractLen, keyBits]
}

אני מקווה שנהניתם מהאתגר והפתרון, אני מאוד מאוד נהניתי
תודה ל @DOVID!

[yossiz]

@חגי אתה צודק, ידעתי מראש שיש מקסימום תיאורטי של כמה ביטים אפשר לחלץ, אתה לא מפתיע אותי

אגב, מה קובע כמה ביטים אפשר לחלץ?

התשובה:
קח את רשימת החזקות של 2 (כלומר 2,4,8,16,32 וכו') סך הביטים שאפשר לחלץ נקבע לפי אורך הביטים של ה-n הכי גבוה מהרשימה הנ"ל שכלפיו יש מספר i ברשימה של המספרים המוצפנים ש-i % n === 0
את ההסבר של החוק הנ"ל אני משאיר לך לשיעורי בית.

תודה על ההזדמנות שנתת לי להרגיש לרגע קט כפרופסור למתמטיקה

[yossiz]

@yossiz אמר בחילוץ מפתח XOR מתוך מספרים ממויינים:

const previous = numList[bestIndex - 1]
const extractLen = bestDiff.toString(2).length
const keyBits = bestDiff ^ (previous ^ (1 << (extractLen - 1))) & makeBitmask(extractLen)

תפסתי אתמול שזה מסובך מדי, אפשר יותר פשוט:

const best = numList[bestIndex]
const extractLen = bestDiff.toString(2).length
const keyBits = (best ^ (1 << (extractLen - 1))) & bestDiff

זה מייתר גם את פוקנצית העזר makeMask