לפי בדיקות שערכו המפתחים, על גרסאות שונות של מעבד פנטיום הצפנת AES על מעבד 200 MHz, צרכה כ-18 מחזורי שעון לבית שזה מקביל בערך ל-11 מגה-בית בשנייה ועל מעבד פנטיום M 1.7 GHz עד 60 מגה לשנייה. ב-2008 הטמיעה אינטל הרחבת סט פקודות לסדרה x86 בשם Advanced Encryption Standard New Instructions בקיצור AES-NI הכוללת פונקציות הצפנה ופענוח AESENC ו-AESDEC המגיעות למהירות של 3.5 cpb. ב-2011 הטמיעה חברת אינטל פונקציות קריפטוגרפיות ממוטבות (IPP) בארכיטקטורת AI שתומכות ב-OpenSSL גרסה 1.0.1 ומעלה. התוצאות שנבדקו בעיקר על מעבד Xeon הגיעו לביצועים של כ-900 מגה בשנייה. (פענוח מהיר יותר ויכול להגיע ל-2.3 ג'יגה לשנייה).
ביטחון הצופן.
במהלך התחרות המקורית של NIST הוכרז על ידי המארגנים שלא נמצאו באף אחד מהפיינליסטים חולשות כלשהן. הסברה הייתה אז שהתקפה מעשית כנגד האלגוריתמים המנויים עם מפתח 128 סיביות היא לא סבירה בטווח של כעשר שנים, אך ההגדרה של התקפה מעשית נתונה לשינויים בהתאם ליכולת טכנולוגית. הערכות שניתנו על ידי מומחים לפני כעשור, הגדירו התקפה מעשית ככזו שמבוצעת עם formula_132 טקסטים ידועים (known plaintext) בסיבוכיות של formula_133 ניסיונות. כיום הועלה הרף מעט יותר. להערכת מומחים formula_134 עדיין נחשב מחוץ להישג יד, אם כי איש לא יודע להעריך לכמה זמן.
לדעת מומחים גם אם מחשב קוונטי יהיה מעשי בטווח הקרוב, סיבוכיות התקפה כנגד האלגוריתמים המנויים באמצעות חישוב קוונטי רק תפחית את המאמץ לחצי (בכללות formula_135 פעולות כאשר formula_136 אורך המפתח), כלומר מפתח 256 עדיין מותיר שולי ביטחון טובים נכון לשנת 2014 ולשנים הקרובות. יתרה מזו, קיימות טכניקות הצפנה מרובה עם מפתחות שונים להגברת הביטחון ולאילו שחוששים במיוחד לחוסנו של האלגוריתם מסוים כנגד התקפות עתידיות, אפשר להגיע לתצורה שבה הצפנה עם מספר אלגוריתמים שונים, תהיה חזקה לפחות כחוזקו של האלגוריתם החזק מביניהם. זאת בהנחה שלא סביר שתמצא דרך לפצח את כולם באותה הקלות.
באופן כללי, הדרך הטובה ביותר לתקוף צופן בלוקים היא הפעלת סוגי התקפות שונות על גרסאות מצומצמות של הצופן, קרי עם מספר קטן יותר של סבבים. משמעות שבירת האלגוריתם היא בעצם מציאת כל דרך אפשרית לחשיפת המפתח, הקצרה ולו במעט מכוח גס. אם כי במרבית המקרים גם אם תמצא דרך כזו, לרוב לא תהיה מעשית ולא תטריד איש בטווח הקרוב. אך מעצם ההגדרה, מהווה נקודת תורפה שיש להתייחס אליה.
ניסיונות התקפה.
ב-2002 פותחה על ידי הקריפטוגרפים קורטויז ופייפרציק שהיה ממפתחי LOKI התקפה על AES הנקראת XSL שמסוגלת לטענתם לפרוץ את האלגוריתם מהר יותר מכוח גס באופן משמעותי. ההתקפה פועלת על ידי גזירת מערכת משוואות ריבועיות מהצופן, שהן פונקציה של הטקסט המקורי, הטקסט המוצפן והמפתח. המערכת מאוד גדולה (כ-8,000 משוואות עם כ-1,600 נעלמים במקרה של AES-128). אלימינציית גאוס מחייבת המצאות כמות מספקת של משוואות בלתי תלויות. הם הציעו פתרון באמצעות טכניקה שהמציאו לצמצום מספר הנעלמים שנקראת eXtended Sparse Linearization המסתמכת על עבודתם של שמיר וקיפניס. יתרון ההתקפה שנדרשת רק כמות מועטה של טקסטים ידועים. אולם הסתבר שהשיטה דורשת משאבים עצומים ואינה יעילה מכוח גס כפי שנטען בתחילה על ידי המפתחים, לכן נקראת תאורטית במובן זה.
במהלך התחרות לתקן המתקדם הביעו מומחים אחדים דאגה מהמבנה האלגברי הייחודי הסגור של ריינדל וכן העובדה שהוא מסתמך על הנחה שטרם הוכחה, שקשה חישובית לפתור מערכת משוואות בעלת מבנה ייחודי כזה. ברוס שנייר שפיתח את Twofish הצהיר שאינו סבור שמישהו יוכל לנצל את המבנה הייחודי הזה לצורך התקפה מעשית כנגד ריינדל.
ב-2009 פותחה על ידי בריוקוב וחובראטוביץ והלוי התקפה על כל גרסאות AES הנקראת התקפת מפתחות קשורים. התקפה מסוג זה מניחה שהתוקף מסוגל לבחור מפתחות שיש ביניהם קשר או יחס כלשהו, כגון אם מפתח אחד הוא XOR של מפתח אחר עם קבוע כלשהו. ההתקפה מתמקדת בתהליך הרחבת המפתח הפשוט יחסית של ריינדל בגרסאות AES-192 ו-AES-256 והגיעה לסיבוכיות של formula_137 וסיבוכיות מקום של formula_138. יש לזכור שמעשית היות שהמפתחות נבחרים באקראי, התקפה כזו אינה סבירה. התקפה דומה שהמציאו המפתחים האמורים יחד עם שמיר, דונקלמן וקלר, כנגד AES-256 מצליחה לחשוף את המפתח רק עם שני מפתחות קשורים, בזמן של formula_139 בתשעה סבבים, formula_140 בעשרה סבבים ו-formula_133 ב-11 סבבים. אף אחת מההתקפות לא יעילה כנגד AES במלוא הסבבים.
נכון ל-2011 ההתקפה הטובה ביותר כנגד AES מלא (14 סבבים במקרה של 256 סיביות) היא של בוגדנוב, חובראטוביץ' ורכנברג. זוהי סוג של 'התקפת נפגש באמצע' הנקראת biclique והיא טובה מכוח גס בפקטור של 4 בקירוב כלומר formula_142 על כן חשיבותה תאורטית והיא אינה מסכנת את השימוש בצופן ריינדל מבחינה מעשית.
התקפת ערוץ צדדי.
נכון ל-2011 התפרסמו מספר התקפות ערוץ צדדי מוצלחות כנגד AES אם כי בעקיפין. סוג זה של התקפה אינו מתמקד בצופן עצמו אלא באופן יישומו במערכת, העשוי שלא במודע להדליף מידע קריטי אודות הצופן או המפתח. באפריל 2005, הכריזו מומחים על התקפת cache timing שהצליחה לפרוץ לשרת ייעודי שיישם הצפנת AES כחלק ממערכת SSL. השרת נבנה כך שיאפשר חשיפה של מידע תזמון רב ככל האפשר. ההתקפה נזקקה ללפחות 200 מיליון צופנים נבחרים. יש הסבורים כי התקפה זו אינה מעשית דרך אינטרנט, ברוס שנייר כינה אותה "התקפת תזמון נאה". באותה שנה, עדי שמיר ושני חוקרים נוספים ממכון ויצמן, פרסמו מסמך המתאר מספר התקפות תזמון דומות כנגד AES ופתרונותיהן. אחת מהן, הצליחה לחשוף את המפתח כולו אחרי 800 כתיבות לזיכרון בלבד תוך מספר מילישניות, בתנאי שלתוקף הייתה גישה לשרת בו מתבצעת ההצפנה.
הדרך הטובה ביותר להתמודדות עם התקפות מסוג זה היא יישום האלגוריתם באופן שאינו מדליף מידע, בעיקר הימנעות משימוש בטבלאות המרה (table lookup) שאמנם משפרות ביצועים אך פותחות פתח להתקפות תיזמון, לשם כך פותחו שיטות כגון Bit Slicing, שיטה ישנה שפותחה על ידי אלי ביהם לשיפור ביצועי אלגוריתם DES והתגלתה כטובה במיוחד כנגד התקפת תיזמון.
מכונת טיורינג הסתברותית
במדעי המחשב, מכונת טיורינג הסתברותית היא מודל מתמטי של מחשב המהווה הרחבה של המודל הסטנדרטי של מכונת טיורינג על ידי הוספת אלמנט הסתברותי לחישוב שהמכונה מבצעת. תוספת זו גורמת לכך שמכונת הטיורינג תפעל על אותו הקלט בדרכים שונות. בניגוד למכונת טיורינג לא דטרמיניסטית שבה קלט מתקבל אם קיים מסלול חישוב כלשהו שבו הוא מתקבל, במכונת טיורינג הסתברותית, לכל קלט קיימת הסתברות לקבלתו או לדחייתו.
הגדרה פורמלית.
קיימות מספר דרכים שונות להגדיר מכונת טיורינג הסתברותית. רוב הדרכים שקולות או שאינן מוסיפות למכונה כוח משמעותי.
כל ההגדרות מתבססות על המודל הרגיל של מכונת טיורינג, אך מוסיפות לו כוח נוסף:
מחלקות סיבוכיות הסתברותיות.
בניגוד למודל הסטנדרטי של מכונת טיורינג (וגם למודל האי דטרמיניסטי שלה), לא ניתן לומר כי מכונת טיורינג הסתברותית "מקבלת" או "דוחה" קלט מסוים. במקום זאת, ניתן לומר שהיא מקבלת אותו בהסתברות כלשהי, ודוחה אותו בהסתברות אחרת. על כן, כאשר מכונת טיורינג הסתברותית בודקת פתרון לבעיית הכרעה כלשהי, היא עשויה לטעות בהסתברות כלשהי (להגיד על פתרון נכון שאינו נכון, או להגיד על פתרון שגוי שהוא נכון). נהוג להגדיר מחלקות סיבוכיות שונות בהתבסס על דרישות מגודל ההסתברות שהמכונה תטעה, ומזמן הריצה הנדרש למכונה.
בצורה דומה להגדרות המחלקות הללו ניתן גם להגדיר מחלקות מקבילות עבור דרישת זיכרון לוגריתמי. המחלקות המתקבלות מסומנות ב-PL,BPL,RL,Co-RL,ZPL.
מהראנגר
פנתינאיקוס אתונה (כדורסל)
פורטו וליו
פורטו וליו (פורטוגזית: Porto Velho - "נמל ישן") היא בירת המדינה הברזילאית, רונדוניה. ממוקמת באגן נהר האמזונאס העליון ואוכלוסייתה מונה 519,531 תושבים (נכון לשנת 2018, על פי נתוני IBGE).
העיר שוכנת בגבול המדינות הברזילאיות רונדוניה ואמזונאס ומהווה מרכז של סחר בקסיטריט, מרכז תחבורה ומרכז תקשורת. העיר ממוקמת על הגדה המזרחית של נהר מדיירה, אחד היובלים העיקריים של האמזונאס.
היסטוריה.
פורטו וליו הוקמה ב-2 באוקטובר 1914 על ידי חלוצים שנשלחו בידי חברת "מסילת הרכבת של מדיירה מאמורה" בסביבות 1907. לאחר שבניית מסילת הרכבת הושלמה, מנתה אוכלוסיית העיר כ-1,000 תושבים ובנייניה היו בעיקר הבניינים של הנהלת מסילת הרכבת ובתי עץ קריביים.
במהלך שישים השנים הראשונות, פיתוח העיר היה קשור ישירות לפעילות הרכבת. העיירה שגשגה במהלך תנופת הגומי, אולם אז כאשר גומי מלזי בעלות נמוכה הפך את הגומי מאמזונס ללא תחרותי, כלכלת האזור נבלמה. ערים כמו סנטו אנטוניו דו מדיירה, שהיו להן קו חשמלי ועיתון שבועי עד להקמתו של פורטו וליו, אינן אלא חורבות בימינו.
ההישרדות של פורטו וליו קשורה לתנאים הטובים יותר של האזור בו הוא נבנה, הגישה הקלה שלו ליד הנהר והנמל שלו: כל אלה היו שיקולים בבחירתה פורטו וליו כבירת הטריטוריה הפדרלית החדשה של גוואפה, בשנת 1943. רק עם תחילת מלחמת העולם השנייה היה מעגל התקדמות נוסף באזור. כאשר כוחות בעלות הברית איבדו שליטה על הגומי המלזי, היה צורך בייצור גומי מהאמזונס לצורך המאמץ המלחמתי. זה ייצר את מה שמכונה בברזיל "בום הגומי השני". אך עם תום המלחמה, שוב נעצרה כלכלת האזור.