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

[חן וייסמן]

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

לדוגמה: הטקסט המקודד הוא uio כאשר המפתח הוא: u=a; i=b; o=c ולכן התוצאה היא abc.

עכשיו, הבעיה היא שהמפתח אינו ידוע.

מישהו מכיר את זה? יכול לעזור?

תודה רבה.

[שניצל]

http://he.wikipedia.org/wiki/%D7%A0%D7%99%D7%AA%D7%95%D7%97_%D7%AA%D7%93%D7%99%D7%A8%D7%95%D7%99%D7%95%D7%AA_(%D7%A7%D7%A8%D7%99%D7%A4%D7%98%D7%95%D7%92%D7%A8%D7%A4%D7%99%D7%94)

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

[חן וייסמן]

כן, נתקלתי בזה... תודה.

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

השאלה האם יש אלגוריתם שיעזור לי לתכנת את זה..

תודה שוב!

[שוקו]

יש לך טקסט ספציפי, או שזה בתאוריה?

[שניצל]

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

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

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

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

לכן, צריך להשתמש באלגוריתמים קצת יותר מתוחכמים.

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

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

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

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

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

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

[TeaTime]

ואין שום סטטיסטיקות על שכיחויות של ספרות (קשה לומר האם הספרה 3 יותר נפוצה מהספרה 2...).

דווקא יש

http://en.wikipedia.org/wiki/Benford%27s_law

[חן וייסמן]

תודה רבה דבר ראשון..

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

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

מישהו פעם תכנת משהו דומה לזה?

[שוקו]

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

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

[שניצל]

^^ גם רעיון טוב.

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

[חן וייסמן]

אוקי.... אז באמת תודה רבה לכל העוזרים..

הורדתי מילון של בערך 150,000 מילים אז אני אלך קודם על מילה של אות אחת ואז 2 ואשווה לפי המילון...