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

[dovid]

@קומפיונט ידעתי גם ידעתי... השתמשתי בXOR לפני 16 שנה כבר...
כוונתי הייתה לפענח מתוך הרצף ללא המפתח. מה שכתבתי מקודם
(אולי הייתי צריך לכתוב לפרוץ, סליחה)

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

ג. לגבי XOR אני מייד חשבתי עליו, אבל בבדיקה שערכתי שמתי לב שאם אני מבקר ביקורים עוקבים המספרים גם הם עוקבים במידה רבה. אני די משוכנע שזה מאפשר לפורץ למצוא את המפתח בקלות, אם מישהו יודע שאני טועה אשמח כי זה הכי קל.
הנה XOR למספרים עוקבים על מספר רנדומלי:
159866
159865
159864
159871
159870
159869
159868
159859
159858
159857

כיון שקל לראות איך נראה כל אחד מהמספרים האלה בינארית, מסתבר שקל לראות מה השתנה בהם ולהסיק מזה איזה סיביות יש במפתח ומה המספר.

[ש.ב.ח.]

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

יש לך עצה קונקרטית עבורי או עבור מישהו אחר איך למנוע את זה להבא?
או שאתה רק מצהיר הצהרה רבת תועלת.

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

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

זה באמת מרגיז כשהעונה לא ירד לסוף דעתך או שחשב להחכים אותי במה שכבר ידעתי ולא שאלתי... וגם השואל לפעמים מרגיש שאולי נראה שלא למד מילה או שנים בתחום מסוים וכבר שואל עליה, ובכל זאת הרבה דרכים לתגובה...

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

סליחה על סטיה מהנושא (פשוט ביקשת... )
א גוטען ערב שבת!

[קומפיונט]

@dovid אשמח אם תיתן לנו אתגר קטן. להיכנס לראש של הפורץ עם ה-30 כניסות ברצף...

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

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

[dovid]

@קומפיונט הבאתי כבר רצף. אני עצמי ניסיתי אבל זה די קשה לי, הראש שלי לא בקטע.
זה XOR פשוט, ואני מושכנע שזה פריץ בקלות.

[קומפיונט]

@dovid התכוונתי לשיטה שאתה מצאת.

[dovid]

פוסט זה נמחק!

[dovid]

@קומפיונט הנה לקוח מהקוד לעיל:

[4413150, 6712083, 9011016, 1309949, 3608882, 5907815, 8206748, 505681, 2804614, 5103547, 7402480, 9701413, 2000346, 4299279, 6598212]

כדי שלא אשכח את המפתח אני שם פה אותו בין כמה אחרים: 7291923, 2298933, 2218933, 1298935.
אגב הרשימה של הXOR הינה אתגר הרבה יותר קל והוא לא הדליק פה מישהו ככל הנראה.

[קומפיונט]

@dovid האם אלו המספרים המקוריים?

[550, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564]

[dovid]

@קומפיונט יפה... אז קבל את האתגר הבא:
6893263, 9174376, 1455489, 3736602, 6017715, 8298828, 579941, 2861054, 5142167, 7423280, 9704393, 1985506, 4266619, 6547732, 8828845

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

[קומפיונט]

@dovid הנה:

551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565

[yossiz]

@קומפיונט אתה הולך לגלות לנו מה השיטה?
(בינתיים לא ניסיתי כלל כי אני עדיין אוחז באתגר הפשוט של מפתח XOR)

[dovid]

@קומפיונט אני בהחלט משתומם!

[dovid]

@קומפיונט עד שתגלה לנו את השיטה, אני נותן לך אתגר נוסף:

57834239, 14151172, 72608117, 28925050, 87381995, 43698928, 15861, 58472806, 14789739, 73246684, 29563617, 88020562, 44337495, 654428, 59111373

[צדיק תמים]

@dovid במה זה שונה מהסדרה הקודמת?

[קומפיונט]

@dovid תצטרך למצוא פתרון חדש עבור האתר, כי אני הולך להרוס לך את הרעיון עקב הבקשה של @yossiz...

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

להלן הקריטריונים שניתנו לשאלה:
א. תרגיל מתמטי פשוט
ב. פשוט וזול למעבד (בפשטות מצריך למנוע שימוש עם BigInt)
ג. עמיד בפני פורץ מיומן
ד. הפורץ יודע את התרגיל
ה. הפורץ יכול להזין 30 כניסות ברצף

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

וזה התרגיל הפשוט שעשיתי, לאחר השערה של הטווח של ה-MAX ושל המספר המפענח. נתתי למחשב לעבוד, הוא מצא את הפתרון אחרי שניה.

[dovid]

@קומפיונט אמר בתרגיל מתמטי של הסתרת מזהה רץ:

לאחר השערה של הטווח של ה-MAX

לא שיערת שום דבר, הMAX היה תמיד זהה.
בשביל זה שמתי לך אתגר נוסף. תן למחשב לעבוד..
(BigInt הוא מאמץ אפסי למחשב).

[קומפיונט]

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

לא שיערת שום דבר, הMAX היה תמיד זהה.

איך יכולתי לדעת?! (משום מה לא הצלחתי לראות את הקוד שלך)

[dovid]

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

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

[dovid]

@צדיק-תמים אמר בתרגיל מתמטי של הסתרת מזהה רץ:

@dovid במה זה שונה מהסדרה הקודמת?

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

[dovid]

זה לא רק עניין של max גבוה.
כעת ניסיתי מספר אחר נמוך בהרבה (פי עשר פחות) רק פחות עגול. וגם אולי במפתח הרנדומלי היה פשוט גבוה בהרבה.
עבור הפלט הזה
699115, 1015520, 310513, 626918, 943323, 238316, 554721, 871126, 166119, 482524, 798929, 93922, 410327, 726732, 21725
הרצתי קוד C# מקבילי (AsParallel().ForAll) על 6 ליבות של I5 11500, ניצולת של 100% מעבדים טוטלית, זה לוקח מלא מלא זמן והוא לא בכיוון.