יצירת מספרים יענו-אקראים.

[Nahum2]

אני צריך אלגוריתם פשוט יחסית שיצור מספרים אקראיים מבחינה קריפטולוגית. מצאתי את האלרותים BLUM BLUM SHUB אבל אני לא מתליח למצוא ישום שלו ב C או C++.

[שניצל]

בבקשה:

http://en.wikipedia.org/wiki/Linear_congruential_generator

[Nahum2]

תודה רבה,

עוד לא קראתי לעומק... כי אני קצת עייף.

נראה טוב הסתובבתי בWIKI שעות ולא מצאתי קישור לזה, איך מצאתה?

[שניצל]

זה פשוט נושא שאני מכיר, אז רק חיפשתי את הלינק הישיר אליו.

[Ghosthunter]

int getrandom()
{
int bla;
return bla;
}

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

[שניצל]

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

אם תקרא ל-getrandom כמה פעמים ברצף, רוב הסיכויים הם שתקבל תמיד אותה תוצאה.

[R9547655G]

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

ממ עד כמה שאני יודע...

[Boomerang]

עניתי על זה כבר פעם.

עריכה:

לא ברור לי מה קרה לקו התחתון בלינקים כאן.

[Nahum2]

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

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

בהנתן רצף ביטים באורך K אם הסיכויים של התוכנה על בסיס ניחוח סטטיסטי ואלגוריתמי קטנים מ 50% רק אז הרצף יחשב בטוח מבחינה קריפטולוגית.

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

[R9547655G]

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

[Nahum2]

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

[Boomerang]

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

משתמשים בזה המון ב"קסמים".

[Zelig]

זהירות!

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

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

הרבה אנשים חושבים שזה פשוט, או חושבים שהם מומחים בזה, ואז עושים טעויות שאחרי זה עולות הרבה כסף. אני לא מומחה, אבל אני לפחות יודע שאני לא מבין בזה כלום. לדוגמא: linear congruential generator שמישהו הציע כאן הוא אולי הסוג הכי גרוע שיש של PRNG מהרבה בחינות, וחלוטין לא מתאים למטרות קריפטוגרפיה. גם linear feedback shift registers (LFSR( לא מתאים כלשעצמו.

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

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

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

[Nahum2]

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

אז מישהו מכיר אלגוריתם פשוט יחסית לCSPRNG?

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

[Zelig]

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

אז מישהו מכיר אלגוריתם פשוט יחסית לCSPRNG?

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

אני שוב חוזר ואומר, PRNG קריפטוגרפי זה לא פשוט. גם אם מישהו יתן לך אלגוריתם כזה אז:

1) אין לך מושג עם הוא אכן טוב. לדוגמא אני יכולתי לתת לך אלגוריתם שאומר: תתחיל עם MT ואז תעשה MD5 hash עם הזמן הנוכחי. זה אולי נשמע טוב, אבל זה לא בהכרח בטוח.

2) אתה עלול לעשות טעויות במימוש.

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

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