תגובה: תרגיל מתמטי של הסתרת מזהה רץ
בהמשך לנושא הנ"ל,
@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')))
נ.ב. אשאיר פה את הקוד בלי הסבר לבינתיים למי שירצה להתעמק לבד...
מחר או מחרתיים יבוא ההסבר בל"נ
לענ"ד יותר קל למצוא את הפתרון באמצעות מחשבה מאשר לנסות לעקוב אחרי הקוד הזה...
עריכה: יש חסרון בקוד. אני מחלץ פחות ביטים מהמקסימום התיאורטי. אתקן בהזדמנות
עדכון: הקוד תוקן סופית. זה אמור להיות מושלם עכשיו
- הימני עבור הכנסת תו LRM והשמאלי עבור תו RLM.