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