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

[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 ייקח הרבה זמן.

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

[קומפיונט]

@dovid החולשה של הפתרון שלך הוא בעיקר בגלל שאפשר לעלות עליו עם Brute Force, וזה בעצם הדבר שהתרגיל שהצגתי עושה אותו (הרבה) יותר קשה.

מבחינת המתמטיקה אני בטוח שאין דרך לפענח את זה. החולשה היחידה האפשרית זה Brute Force.

[dovid]

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

החולשה של הפתרון שלך הוא בעיקר בגלל שאפשר לעלות עליו עם Brute Force

בינתיים לא הצגת קוד זהב שעושה זאת בלי שום ידע מוקדם מלבד הנקודות שזהכרת (השיטה והרצף של ה30).

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

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

[קומפיונט]

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

בינתיים לא הצגת קוד זהב שעושה זאת בלי שום ידע מוקדם מלבד הנקודות שהזכרת (השיטה והרצף של ה30).

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

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

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

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

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

[קומפיונט]

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

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

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

מה, וכי אני אשם שה-RSA משתמש בתרגיל המתמטי הפשוט הזה?!

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

[קומפיונט]

אני רוצה להוסיף עוד משהו קטן.

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

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

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

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

אפשר לקרוא על זה פה תחת התת כותרת "ריפוד".

[dovid]

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

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

var numsEncrypted = new[] { 42993, 630, 40082, 9071, 54161, 15738, 51342, 25721, 52199, 49738, 50927, 13700, 37966, 3174, 35345 };

var primes =
    from n in Enumerable.Range(128, 512).AsParallel()
    where Enumerable.Range(2, (int)Math.Sqrt(n)).All(i => n % i > 0)
    select n;

var arr = primes.ToArray();
var allN = arr.SelectMany(a => arr.Select(x => x * a)).Distinct();


var st = Stopwatch.StartNew();
var keyD = allN.SelectMany(n => Enumerable.Range(1, 1000).Select(d => (n, d))).AsParallel().Where(e => TestNumber(e.d, e.n)).First();
st.Stop();
Console.WriteLine(st.Elapsed);
Console.WriteLine($"key founded: N: {keyD.n}, D: {keyD.d}");

foreach (var e in numsEncrypted)
    Console.WriteLine(BigInteger.Pow(e, keyD.d) % keyD.n);




bool TestNumber(int d, int n)
{
    var prev = BigInteger.Pow(numsEncrypted[0], d) % n;
    if (prev > 10000)
        return false;

    for (var o = 1; o < numsEncrypted.Length; o++)
    {
        var temp = BigInteger.Pow(numsEncrypted[o], d) % n;
        if (temp > 10000 || (temp - prev) != 1)
            return false;

        prev = temp;
    }

    return true;
}

[קומפיונט]

@dovid אני אוהב לעזור לכל מי שמבקש, התחום שאני חזק בו זה #C ו WPF, ובינתיים לא נתקלתי בבקשת עזרה בתחום הזה. אם אני יתקל בבקשת עזרה בתחום הזה, אהיה בל"נ הראשון שיעזור.

רוב השאלות שראיתי פה בפורום הם בנושא VBA או WinForm שאני לא מומחה בהם, בלשון המעטה.

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

קח לדוגמא את הספרות האלו:
1194494
719311
1944435
1477276
874876
1765046
1615810
1097120
1085181
1495561
1968819
1743848
171395
217310
1476345

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

[dovid]

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

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

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

[mekev]

@mekev

אנקדוטה מעניינת לסיום השרשור

תראו איך האלגוריתם של גוגל פיענח את התוכן

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

[yossiz]

@mekev יהיה באמת מעניין להבין מה גרם לגוגל לבחור באתר הזה, זה נראה התקף פסיכוטי של גוגל

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

[איש נחמד]

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

@mekev יהיה באמת מעניין להבין מה גרם לגוגל לבחור באתר הזה, זה נראה התקף פסיכוטי של גוגל

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

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

וזה :

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