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

[צדיק תמים]

@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% מעבדים טוטלית, זה לוקח מלא מלא זמן והוא לא בכיוון.

[קומפיונט]

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

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

אני הרצתי את הרצף ספרות האלו בתרד אחד והתשובה הגיעה אחרי חצי דקה.

זה הרצף:
551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563, 564, 565

וזה המודולו:
1021412

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

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

[קומפיונט]

@dovid במקור האחרון שהבאת מציינים במפורש שזה לא מוסיף אבטחה.

תראה את הפסקה האחרונה:

Hopefully it’s obvious that this adds no actual security to a system; it’s obscurity, at best.

[dovid]

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

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

תודה על השיעור המאלף.

[חגי]

@dovid מהנושא שיוסי פתח, בינתיים נראה שמפתח מאוד גדול עם XOR כן יפתור את הבעיות, ידוע לך על אלגוריתם שיכול לפרוץ את זה?

[dovid]

@חגי אני יצטרך ללמוד את ההודעות ש@yossiz הנפלא כתב, עד אז אני מנוע מלהתייחס...
שים לב 1) שאני חושש מפריצה בגלל תחושה אינטואטיבית, אני בכלל לא ידעתי דרך לפרוץ גם קודם. 2) אני הייתי עסוק כפי שאתה רואה בדיון עם @קומפיונט על אפשרות של פריצה עם כח גס, בזה ודאי שיש לxor חיסרון.

[dovid]

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

אני הרצתי את הרצף ספרות האלו בתרד אחד והתשובה הגיעה אחרי חצי דקה.

@קומפיונט אמר בתרגיל: עיגול מספר לפי מערך מפתחות:

העניין הוא מאיזה מספר להתחיל את הסריקה. לא התחלתי מאפס, כמובן.

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

[קומפיונט]

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

אולי תגיד בדיוק מה עשית במקום שאני אעשה לך שש מבחנים?

כשאני מסתכל על רצף הספרות שעברו ערפול, לדוגמא:

699115, 1015520, 310513, 626918, 943323, 238316, 554721, 871126, 166119, 482524, 798929, 93922, 410327, 726732, 21725

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

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

[dovid]

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

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

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

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

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

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

[קומפיונט]

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

שגוי לחלוטין. אין לך קצה חוט בעניין, מלבד הדוגמאות פה...

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

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

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

כל הנושא הזה זה נשמע לי כמו מתקפה, אז הגבתי בהתאם.

[קומפיונט]

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

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

היצירה של המפתחות בפעם הראשונה היא פעולה קצת מורכבת, אז הכנתי פונקציה ב-#C שתיצור את המפתחות.
יש שלושה מפתחות: d ,e ו - n, ה - n הוא המודולו והוא המספר המקסימלי שאפשר לערפל ולשחזר למספר המקורי.
אחרי שיש את המפתחות הערפול נעשה בצורה כזאת: id ** e % n והשחזור למספר המקורי נעשה הפוך: obfuscated ** d % n

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

זה הפונקציה ליצירת המפתחות: (GenerateKeys)

void GenerateKeys(out int n, out int e, out int d)
{
    Random random = new();

    int p = GeneratePrime(128, 512, random);
    int q = GeneratePrime(128, 512, random);

    n = p * q;
    int ef = Lcm(p - 1, q - 1);

GenerateE:
    e = random.Next(32, 512);

    if (Gcd(e, ef) != 1)
        goto GenerateE;

    d = GenerateD(ef, e);

    if (d < 0)
        goto GenerateE;
}

bool IsPrime(int num)
{
    for (int i = num - 1; i > 1; i--)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

int Gcd(int a, int b)
{
    return b == 0 ? a : Gcd(b, a % b);
}

int Gcf(int a, int b)
{
    while (b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int Lcm(int a, int b)
{
    return a / Gcf(a, b) * b;
}

int GeneratePrime(int min, int max, Random random)
{
    int p;

    do
    {
        p = random.Next(min, max);
    } while (!IsPrime(p));

    return p;
}

int GenerateD(int ef, int e)
{
    int y1 = 1, y2 = 0;

    while (e > 0)
    {
        int q = ef / e;
        int y = y2 - (q * y1);
        int r = ef % e;

        ef = e;
        e = r;

        y2 = y1;
        y1 = y;
    }

    return y2;
}

בשביל למהר את הביצועים מומלץ להשתמש במפתחות עם המודולו הקטן ביותר שנצרך, לדוג' אם המספר הגבוה ביותר שצריך לעפל הוא 10,000, אז כדי לקרוא לפונקציה שיוצרת את המפתחות שוב ושוב עד שיצא מספר מקסימלי (n) הכי נמוך אבל מעל 10,000.

טסט לדוגמא ב-#C:

GenerateKeys(out var n, out var e, out var d);

Console.WriteLine($"n: {n}, e: {e}, d: {d}");

foreach (var num in Enumerable.Range(3, 15))
{
    int c = (int)(BigInteger.Pow(num, e) % n);
    int m = (int)(BigInteger.Pow(c, d) % n);

    Console.Write("num: " + num);
    Console.CursorLeft = 15;
    Console.Write("c: " + c);
    Console.CursorLeft = 30;
    Console.WriteLine("m: " + m);
}

הפלט:

n: 71219, e: 287, d: 12683

num: 3         c: 36878       m: 3
num: 4         c: 51738       m: 4
num: 5         c: 44630       m: 5
num: 6         c: 54772       m: 6
num: 7         c: 26540       m: 7
num: 8         c: 21046       m: 8
num: 9         c: 60079       m: 9
num: 10        c: 43447       m: 10
num: 11        c: 66289       m: 11
num: 12        c: 36954       m: 12
num: 13        c: 61380       m: 13
num: 14        c: 64087       m: 14
num: 15        c: 65269       m: 15

אשמח לקבל הארות ותגובות.

[dovid]

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

אבל הוא הרבה יותר בטוח וקשה לפענוח.

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

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

[קומפיונט]

@dovid
קשה לי להסביר למה הוא יותר טוב (משום שלי לא ברור עד הסוף), אבל הוא בטוח יותר טוב מסיבה פשוטה:
מתבצע בו העלאה בחזקה (במקום הכפלה בתרגיל שלך) שזה לוקח זמן למחשב, ולכן ל-Brute Force ייקח הרבה זמן.
לדוגמא, התוצאה של התרגיל הזה: 12345 ** 12345 זה מספר עם 50,510 ספרות, אז בשביל פעם אחת האיטיות לא תהיה מורגשת, אבל לחישוב של אלפי מספרים האיטיות תהיה מורגשת מאוד.

אבל זה גם לא מאה אחוז. ככל שהמספרים של המפתחות יהיו גדולים כך זה יהיה יותר בטוח (אבל גם איטי).

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

יש לך מה להשתפשף בקידוד, כי הקוד לא מספיק טוב

אשמח אם תצביע לי על מקום שיכול להיכתב יותר טוב, ואני בל"נ אתקן.

[dovid]

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

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

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

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