stanford-oval/wikipedia huggingface dataset:
ראש עיריית מונמות'
רשימת ראשי עריית מונמות'

פרק זה לוקה בחסר. אנא תרמו לוויקיפדיה ו. ייתכן שתמצאו פירוט בדף השיחה.
1675 – ריצ'רד באלארד
1744 – ויליאם ויליאמס
1785 – ויליאם ססל
1786 – לוק פיליפס
1787 – תומאס מוריסון (?)
1806 – תומאס פרוסר
1819 – צ'ארלס הית
1820 – הכומר תומאס פרוסר
1821 – צ'ארלס הית
1822 – חזקיה סוויפט
1836–1837 – תומאס ווטקינס
1838–1839 – תומאס פרוסר
1839 – תומאס דייק
1840–1841 – ג'ון ליץ' ניקולס
1842–1843 – ג'ורג' ויליס
1844–1845 – ג'יימס פירס קינג
1852 – ג'ון מאיו
1860–1861 – ג'ון ליץ' ניקולס
1862–1863 – ג'ורג' וויליס MD
1864–1865 – ג'יימס פירס קינג
1870–1873 – אלכסנדר רולס
1874 – תומאס ג'ונס בייקר
1875–1876 – תומאס ריצ'רד הייאם
1877 – ג'וזף קואטס
1879 – ארתור וויזארד
1880 – GP טיפינס
1883–1885 - שמפני פאוול
1889 – ויליאם הול
1891–1896 – ויליאם האניפילד
1896 – ג'ון רולס, הברון הלנגאטוק הראשון
1896–1898 – אלוף-משנה ג'ה וואלווין
1899–1900 – ג'יימס האוס
1900–1903 – המילטון טררן באלי
1903–1904 – GR אדוארדס
1906–1907 – מייג'ור ג'ון רולס, הברון הלנגאטוק השני
1908–1909 – ו. סמברוק
1914 – ו. בנטינג
1910 – ו. סמברוק
1921 – א.ט. בלייק
1934 – צ'ארלס ג'יימס ג'ונס
1950–1953 – ברנרד פרטרידג'
1954–1955 – סטנלי הווארד בואן
1956–1957 – ג'יימס בנג'מין ברייקוול
1958–1959 – ריצ'רד פריס ברנט תומאס
2009 – טרי כריסטופר
2010 – אן היו
2011 – אולם ג'אנה
2012 – גרי ברייט
2013 – אולם ג'אנה
2014 – ג'יין גונטר
2015 – גרהם פריצ'רד
2019 – ריצ'רד רודן
2020 – מאט פיקינס
ראו גם

מונמות'
ראש עיר
הערות שוליים

↑  [https://books.google.co.il/books?id=MrA5AQAAIAAJ&q=%22william+sambrook%22+monmouth&dq=%22william+sambrook%22+monmouth&redir_esc=y&hl=iw
ביקורת שופטת השלום והשלטון המקומי, כרך 92]
↑  מועצת העיר מונמות
רובע מונמות', רשימת ראשי הערים, מוצג באולם שייר, מונמות'
בעיית RSA

בקריפטוגרפיה, בעיית RSA היא הבסיס התאורטי להצפנת RSA, שהומצאה על ידי שמיר, ריבסט ואדלמן ב-1977, ונמצאת מאז בשימוש מאסיבי בכמעט כל מערכת הצפנה מודרנית. בעיית RSA היא בעיה בתורת המספרים שאפשר לנסחה בקיצור: "מציאת שורש ממעלה  e של  c מודולו  n".
מודולוס RSA

בהצפנת RSA אליס מצפינה את המסר הגלוי  M עבור בוב באמצעות המפתח הציבורי של בוב  (n,e) על ידי חישוב:
n נקרא מודולוס RSA והוא בדרך כלל כפולה של שני ראשוניים  p ו- q אקראיים, גדולים ושווים בגודלם בקירוב.  e נקרא מעריך ציבורי והוא שלם אי-זוגי  e\geq 3, שצריך להיות זר ביחס ל- \phi (n) שהוא פונקציית אוילר המייצגת את הסדר של החבורה הכפלית  \mathbb {Z} _{n}^{*}. היות שהסדר של  p הוא  p-1 וכן לגבי  q הרי ש- \phi (n)=(p-1)(q-1). פונקציית RSA היא מהצורה  f(x)=x^{e}{\text{ (mod }}n). השלם  d הוא הופכי כפלי של  e ביחס לסדר  \phi  ונקרא גם דלת המלכודת. המפתח הפרטי הוא אם כן הצמד  (n,d).
בוב שברשותו המפתח הפרטי יכול לפענח את  C כיוון ש- de\equiv 1{\text{ (mod }}\phi (n)) ומזה נובע ש- C^{d}\equiv M^{ed}\equiv M{\text{ (mod }}n).
יריב פוטנציאלי יכול לנסות לגלות מהו  C על ידי ציתות לרשת וייתכן אף שהמפתח הציבורי של בוב ידוע לו. ההנחה היא שלמרות האמור יהיה קשה לו לחשוף את  M או את  d.
ניסוח פורמלי של הבעיה

המגבלות שהוטלו על הפרמטרים מבטיחים שלכל  C קיים אך ורק  M יחיד המתאים לו, כלומר  \ f(x)=x^{e}\ {\mbox{mod }}n היא תמורה ב- \mathbb {Z} _{n}. הפונקציה gcd היא מחלק משותף מקסימלי. היריב, שהמפתח הפרטי אינו ידוע לו, חייב להפוך את פונקציית RSA. חיפוש סדרתי של הפונקציה ההופכית  f^{-1}(C)\ {\mbox{mod }}n מחייב בממוצע בדיקת כמעט כל המעריכים האפשריים. אם המעריך גדול המשימה תהיה בלתי מעשית.
השערת RSA

השערת RSA מניחה שבעיית RSA המתוארת קשה לפתרון במידה והתנאים הבאים מתקיימים: הגורמים הראשוניים של המודולוס אינם ידועים לתוקף, המודולוס גדול מאוד, המודולוס נוצר באקראי (הגורמים נבחרו באקראי) וכן המסר  M (ומזה נובע גם הצופן  C) ממופה לאלמנט אקראי ב- \mathbb {Z} _{n}^{*}, דהיינו בטווח  [0,n-1].
השערה זו זהה לטענה שפונקציית RSA היא חד-כיוונית עם דלת מלכודת כשהמפתח הפרטי הוא דלת המלכודת. דהיינו בעוד שקל לחשב חזקה ממעלה  e של  x (מודולו  n), הרי שקשה לבצע את הפעולה ההפוכה, לחשב את השורש ממעלה  e של  C מודולו  n. אלא אם כן יינתן רמז סודי שהוא במקרה זה  \phi (n).
אקראיות  M חשובה כיוון שאם ידוע ש- M נבחר מתוך טווח קצר, היריב יכול לנסות לפענח את  C פשוט על ידי ניסוי כל האפשרויות (מבלי צורך להפוך את פונקציית RSA כלל).
גם אם  M נבחר באקראי היריב יכול למפות את כל האלמנטים ב- \mathbb {Z} _{n}^{*} עד שהוא נתקל ב- M הנכון. אולם התקפת כוח גס מסוג זה היא מעריכית, עם זמן ריצה בסדר גודל של  {\text{log}}_{2}\ n. בטכנולוגיה הנוכחית ועם מספרים גדולים (כמה אלפי ספרות) אלגוריתם כזה אינו יעיל.
הקשר לפירוק לגורמים > תכונת המעגליות

בשל העובדה שהצפנת RSA הנה תמורה ב- \ \mathbb {Z} _{n}, אם  C=M^{e}{\mbox{ mod }}n קיים שלם  k המקיים  C^{e^{k}}\equiv C\ ({\mbox{mod }}n). מאותה סיבה  C^{e^{k-1}}\equiv M\ ({\mbox{mod }}n). אם  \ n קטן חיפוש סדרתי של  k כזה אפשרי. אפשר להתחיל בערך נמוך ולקדם את  k עד שהמשוואה האמורה מתקיימת. יתרה מזו, ניתן לייעל את ההתקפה על ידי מציאת השלם  \ u העונה על הדרישה  {\mbox{gcd}}(C^{e^{u}}-C,n)>1. יש סיכוי טוב למצוא את  \ u בפחות מהזמן הדרוש למצוא את  \ k. אם  C^{e^{u}}\equiv C מודולו אחד מהגורמים הראשוניים של  \ n, אזי  {\mbox{gcd}}(C^{e^{u}}-C,n) הוא גורם ראשוני של  n וכאמור ידיעת הגורמים הראשוניים מספקת לחילוץ מפתח הפענוח. במקרה ש- {\mbox{gcd}}(C^{e^{u}}-C,n)=n אזי מתקיים בהכרח  u=k וכאמור  C^{e^{u-1}}\equiv M, במקרה כזה מתקבל  \ m בלא צורך במפתח הפענוח כלל. למעשה אפשר לראות בשיטה זו כדרך שונה לפירוק  n לגורמים. כאמור, פירוק לגורמים היא בעיה קשה כך שתכונה זו אינה מהווה איום משמעותי על אלגוריתם RSA.
מספרים ראשוניים

כאמור חשוב שהמספרים הראשוניים ייבחרו באקראי. לא מומלץ למשל להשתמש ברשימת מספרים ראשוניים מפורסמת, כיוון שבדרך זו מועבר מידע ליריב פוטנציאלי. בבחירת מספרים ראשוניים רצוי שיהיו לא רק אקראיים אלא גם קשים לניחוש. אילו הגדרות שונות, כיוון שאקראיות לבדה אינה מבטיחה קושי בניחוש. על כן השיטה המקובלת היא הפעלת מחולל אקראי בטוח ליצירת מספר אי-זוגי אקראי באורך הרצוי ובדיקת ראשוניותו, מכיוון שבדיקת ראשוניות קלה יותר מפירוק לגורמים, אם המספר מתגלה כפריק מנסים שוב עם מספר אחר. הסיכויים הם שתוך מספר ניסיונות קצר בערך כמספר הספרות, יימצא ראשוני. כמו כן רצוי ש- p ו- q יהיו בגודל זהה בקירוב, כלומר שלמודולוס  n לא יהיו גורמים קטנים כלשהם. זאת כדי לסכל אפשרות שימוש באלגוריתם פירוק שמנצל את קיומם של גורמים קטנים. מצד שני רצוי שההפרש ביניהם לא יהיה קטן מדי. כי אם  p\approx q, אזי גם  p\approx {\sqrt {n}} ואז ניתן למצוא אותם בחיפוש קל, קרוב לשורש.
יש הממליצים להשתמש במספרים ראשוניים חזקים.  \ p הוא מספר ראשוני חזק אם הוא מקיים את ההגדרות הבאות:
\ p-1 מכיל גורם ראשוני גדול  \ r.
\ p+1 מכיל גורם ראשוני גדול כלשהו.
\ r האמור גם הוא, מכיל גורם ראשוני גדול כלשהו.
הוכח מעשית שאין צורך במספרים ראשוניים חזקים, משום שמספרים ראשוניים גדולים מאוד שנבחרו אקראית בדרך בטוחה, כמעט תמיד נוטים לענות על דרישות אלו.
חשיפת המפתח הפרטי לעומת פירוק לגורמים

ההוכחה פשוטה. אם  d ידוע אפשר לחשב את  k=de-1. ידוע ש- k צריך להיות כפולה של הסדר  \phi . היות ש- \phi  זוגי, אם כותבים את  k כ- 2^{t}r כאשר  r אי-זוגי ו- t\geq 1, מתקיים  g^{k}\equiv 1 עבור כל  g\in \mathbb {Z} _{n}^{*} ולכן  g^{k/2} הוא שורש ריבועי של  1 מודולו  n. לפי משפט השאריות הסיני ל- 1 ארבעה שורשים ריבועיים מודולו  n=pq. שניים הם  \pm 1 האחרים הם  \pm x כאשר  x מקיים  x\equiv 1{\text{ mod }}p וכן  x\equiv -1{\text{ mod }}q. בעזרת אחד משני השורשים האחרונים אפשר לגלות את הגורמים של  n על ידי חישוב  {\text{gcd}}(x-1,n) (gcd היא מחלק משותף מקסימלי). אפשר לראות שאם  g נבחר באקראי, אחד מהאלמנטים ברצף  g^{k/2},g^{k/4},...,g^{k/2^{t}} מודולו  n הוא שורש ריבועי של  1 בהסתברות של לפחות חצי. כל האלמנטים ברצף האמור ניתנים לחישוב בזמן של  {\text{log}}_{2}\ n.
הטענה ההפוכה נובעת ישירות מהעובדה שבהינתן הגורמים הראשוניים אפשר לחשב את  \phi  ואת  d. מזה נובע שבעיית פירוק לגורמים שקולה לחשיפת המפתח הפרטי, כך שאין טעם להסתיר את המפתח הפרטי ממי שהגורמים ידועים לו וכן להפך. מסיבה זו לא יהיה חכם לשתף מודולוס אחד לכמה משתמשים (כך שרק המפתחות הפרטיים והציבוריים שלהם שונים). כי בידי כל אחד מהם מספיק מידע כדי לפרק את  n לגורמים ואז הוא יכול לחלץ את המפתחות הפרטיים של כל האחרים מתוך המפתחות הציבוריים שלהם.
מעריך d קטן

בפענוח סיבוכיות פעולת ההעלאה בחזקה המודולרית, ליניארית ביחס לאורכו של  d בסיביות, מסיבה זו אם המפתח הפרטי קטן משיגים שיפור ביעילות הפענוח בפקטור משמעותי. התקפה מתוחכמת של מייקל ויינר מראה שעם מפתח פענוח קטן אפשר לשבור את המערכת כולה בקלות. הטענה היא:
ההתקפה של ויינר מבוססת על קירוב שברים משולבים. היות ש- ed שקול ל- 1 מודולו  \phi  קיים  k המקיים  ed-k\phi =1. מתקיים יחס הקירוב:
השברים  k/d נותנים קירוב טוב של  e/n על ידי התכנסות השבר המשולב. התוקף יכול לחשב את ההתכנסויות עבור  e/n. אחד מהם יהיה שווה ל- k/d ולאור האמור צריך להיות  {\text{gcd}}(k,d)=1 ולכן  k/d הוא שבר מצומצם. האלגוריתם של ויינר מאפשר חילוץ  d בזמן ליניארי. אם  n באורך 1024 סיביות  d חייב להיות לפחות 256 סיביות כדי לסכל התקפה זו. לחלופין אפשר להגדיל את  e על חשבון  d. ויינר הראה שאם  e>n^{1.5} ההתקפה שלו לא תצלח. על כל פנים הגדלת  e אינה פותרת את בעיית היעילות אלא מעבירה אותה להצפנה. ייתכן ושיטה זו תהיה יעילה במקרים בהם המחיר שווה את התועלת, אם אין חשיבות לגודל מפתח ההצפנה לעומת מפתח הפענוח.
ייעול ההצפנה והפענוח מבלי להסתכן בהתקפה של ויינר, אפשרי באמצעות משפט השאריות הסיני כפי שמובא בתקן PKCS. אם מחלקים את  d לשני מפתחות פענוח כך שמתקיים  d_{p}\equiv d{\text{ mod }}(p-1) וכן  d_{q}\equiv d{\text{ mod }}(q-1) ואורך כל אחד מהם מחצית מאורך המודולוס. אזי הפענוח מתייעל בפקטור של שניים בקירוב. בפענוח משתמשים במשפט השאריות הסיני כדי לפתור את מערכת השקילויות  M_{p}\equiv c^{d_{p}}{\text{ mod }}p וכן  M_{q}\equiv c^{d_{q}}{\text{ mod }}q כדי לחשב את  M. והרעיון הוא שהמפתחות  d_{p} ו- d_{q} קטנים לכן העלאה בחזקה עם מפתחות אילו יעילה יותר. לא ברור האם השיטה הזו מחזקת או מחלישה את RSA.
החסם שהציע ויינר אינו מדויק. בונה ואחרים הוכיחו שכל עוד  d<n^{0.292} אפשר לשחזר את  d מתוך  (n,e). בכל אופן החסם המדויק הוא שאלה פתוחה.
מעריך e קטן

משיקולי יעילות מקובל שהמעריך הציבורי יהיה קטן, זאת מבלי לפגוע בביטחון המערכת. הדבר חשוב במיוחד כאשר מיישמים את RSA בחומרה כמו כרטיס חכם.  e=2^{16}+1 נפוץ ביישומים מעשיים, יתרונו במשקלו הבינארי הנמוך. יש לשים לב שאם המסר עצמו קטן גם הוא, ייתכן שיהיה אפשר פשוט לחשב את השורש ממעלה  e של המסר ללא המודולוס (אם  M<{\sqrt[{e}]{n}}). משפט קופרשמידט אומר:
כלומר אפשר לחשב כל השורשים של  f מודולו  n הנמוכים מ- X=n^{1/d}. ככל ש- X קטן זמן הריצה קטן בהתאם. הרעיון של קופרשמידט מבוסס על LLL (אלגוריתם לצמצום סריגים) וזמן הריצה שלו נשלט בידי הזמן שלוקח ל-LLL לרוץ על סריג בעל מימד  O(w) כאשר  w={\text{min}}(1/\epsilon ,{\text{log}}_{2}\ n). הוא טוב במקרה שמנסים למצוא שורשים קטנים מודולו מספר פריק ויש לו השלכות גם בתחומים אחרים (במקרה של מספר ראשוני אין צורך בכך כי קיימות שיטות יותר טובות). על כל פנים ההשלכה של משפט זה שניתן לפתח התקפה על RSA כאשר המעריך הציבורי  e קטן, כדלהלן.
אם השולח מצפין מסר  m מספר פעמים עבור  i משתמשים, כל אחד עם המפתחות המתאימים  (n_{i},e_{i}) שלהם, אם כל  e_{i} שווים ל- e שלם קטן (נניח  e=3), הרי שיריב שמסוגל ליירט את המסרים המוצפנים יכול לחלץ את המסר המקורי על ידי משפט השאריות הסיני ברגע שיצליח להניח ידו על לפחות  e מהם. משום שעבור המסרים  C_{1},C_{2},C_{3},... קיים שלם  C'\in \mathbb {Z} _{n_{1}\cdot n_{2}\cdot n_{3}\cdots } כך ש- C'\equiv M^{e}{\text{ mod }}n_{1}n_{2}n_{3}\cdots . לפי משפט קופרשימדט  M יהיה השורש ממעלה  e (מעל השלמים) של  C'. גם אם השולח ייפרד את  M על ידי סכימת ריפוד ידועה כלשהי (אם הריפוד הוא ערך קבוע עבור כל משתמש) ההתקפה עדיין ישימה. לכן הריפוד חייב להיות אקראי כדי לסכל את ההתקפה האמורה.
התקפה אחרת של פרנקלין וריטר על RSA עם מעריך  e קטן, מנצלת קשר או יחס בין מסרים. כלומר אם לדוגמה השולח מצפין שני מסרים  m_{1},m_{2} כאשר  m_{2} הוא פונקציה ידועה כלשהי מהצורה  f=ax+b של  m_{1}. וכן  c_{1}=m_{1}^{e}{\text{ mod }}n. ידוע ש- m_{1} הוא שורש של הפולינום  g_{1}(x)=f(x)^{e}-c_{1} וכן  m_{2} הוא שורש של  g_{2}(x)=x^{e}-c_{2}. הגורם הליניארי  x-m_{2} מחלק של שני הפולינומים. לאור זאת אפשר להשתמש באלגוריתם אוקלידס כדי לחשב את  m_{2}={\text{gcd}}(g_{1},g_{2}). ההשלכה של התקפה זו הפכת חמורה יותר אם סכימת הריפוד אינה בטוחה. אם השולח מרפד את המסר  m לפני המשלוח על ידי הוספת מספר אקראי קצר  r לסוף המסר הרי שאם יעלה בידי התוקף להשיג מסר  M כלשהו שנשלח פעמיים (עם ריפוד שונה, דהיינו  m_{1}=2^{z}M+r_{1} וכן  m_{2}=2^{z}M+r_{2} כאשר  z הוא אורך הריפוד בסיביות), הוא יכול לבצע את ההתקפה האמורה ולחלץ את  M. כיוון שאם מגדירים את הפולינומים  g_{1}(x,y)=x^{e}-c_{1} וכן  g_{2}(x,y)=(x+y)^{e}-c_{2}, ידוע שאם  y=r_{1}-r_{2} הרי ש- m_{1} יהיה שורש משותף של שניהם שאותו אפשר למצוא בעזרת אלגוריתם קופרשמידט אם הוא קטן.
ראוי לציין שאם המעריך גדול ההתקפות האמורות אינן יעילות. דרך אחרת לסכל התקפות אילו היא לרפד את המסר בסכימת ריפוד אקראית בטוחה. למרות זאת בגלל ההתקפות המתוארות התקנים הידועים נמנעים באופן כללי משימוש במפתחות הצפנה או פענוח קטנים.
מעריך e קטן > חשיפה חלקית של d כאשר e קטן

בונה ואחרים הוכיחו שאם עלה בידי התוקף לגלות חלק (למשל רבע) מסיביות המפתח הסודי  d הרי שהוא יכול באמצעותם לגלות את המפתח הסודי כולו בתנאי שמפתח ההצפנה מקיים  e<{\sqrt {n}}. עובדה זו נובעת ממשפט קופרשמידט שהוכיח שאם יעלה בידי התוקף לנחש נכונה כרבע מסיביות אחד הגורמים הראשוניים של המודולוס, ביכולתו לפרק את המודולוס כולו לגורמים בזמן של  e{\text{ log}}_{2}\ e ניסיונות.
בנוסף אפשר לראות שאם המעריך  e קטן מערכת RSA מדליפה כמחצית מהסיביות המשמעותיות של המפתח הפרטי  d. הסיבה היא בשל המשוואה  ed-k(n-p-q+1)=1 עבור  0<k\leq e. בהינתן  k כאמור התוקף יכול לחשב את  {\hat {d}}=\lfloor (kn+1)/e\rfloor  ואז את
לכן  {\hat {d}} הוא קירוב טוב של  d. דהיינו ברוב המקרים מחצית הסיביות המשמעותיות של  {\hat {d}} זהות לסיביות של  d. היות שקיימים רק  e ערכים אפשריים של  k אפשר לבנות טבלה קטנה של  e כניסות כך שאחד מהאלמנטים בה שווה למחצית השמשעותית של סיביות  d.
כפליות (Multiplicative)

אם  m_{1},m_{2} הם מסרים כלשהם שהטקסטים המוצפנים המקבילים להם הם  c_{1},c_{2} בהתאמה. אזי מתקיימת הזהות הבאה:
תכונה זו נקראת גם הומומורפיזם והיא מאפשרת במצב מסוים התקפה שבה לתוקף גישה חלקית למערכת ההצפנה (אין לו גישה למפתח ההצפנה) אם  c=M^{e}{\mbox{ mod }}n וברצונו לחשוף את  C ביכולתו להסתירו על ידי הכפלת הטקסט המוצפן ב- x^{e} כלשהו כך:  s=Cx^{e}{\mbox{ mod }}n, אם המערכת תפענח עבורו את  s בלא ידיעת הקשר שבינו לבין  C הוא יקבל את:  t=s^{d}{\mbox{ mod }}n. תוצאה זו מאפשרת חילוץ  C בשל הזהות הבאה:
ולכן  M=tx^{-1}{\mbox{ mod }}n. כלומר מסירים את  x על ידי הכפלה בהופכי שלו כדי לקבל את הטקסט מקורי. תכונה זו שימושית גם לטכניקת הסינוור להלן כנגד התקפת ערוץ צדדי. הדרך הטובה ביותר למנוע חולשות עקב תכונת הכיפליות היא לרפד את המסר באמצעות סכימת ריפוד בטוחה.
פריקות עצמית

לאור תכונת הכפליות, לפונקציית RSA תכונת "פריקות עצמית" (Self-reducibility) או רדוקציה עצמית, כלומר תמיד מתקיים:
כך שאפשר למעשה להמיר טקסט מוצפן נתון  M^{e} לטקסט מוצפן אחר  (MR)^{e} כאשר R אקראי. כעת היות שיש סיכוי שהתוצאה תהיה "חלשה" במובן שייתכן שתהיה דרך קלה לפענחה, הרי שהתוקף יכול לנצל עובדה זו כדי לפענח כל טקסט מוצפן. הוכח שאם קיים אלגוריתם  {\text{A}} שיכול לפענח חלקיק קטן  \epsilon  מסך כל ההצפנות האפשריות, הרי שקיים אלגוריתם אקראי אחר  {\text{A}}' שיכול לפענח את כל המסרים המוצפנים באותה סיבוכיות זמן בערך.
מצד אחד תכונת הפריקות העצמית מלמדת שאפשר לצפות מכך שהרוב המכריע של הטקסטים המוצפנים יהיה קשה לפענוח באופן כמעט שווה, תכונה שהועילה בהוכחת ביטחון מספר מערכות הצפנה אסימטרית המבוססות על RSA. אולם מאידך היא נותנת כלים טובים בידי התוקף, היא מאפשרת לגלות טקסט מוצפן אחד מתוך טקסט מוצפן אחר. זו אחת הסיבות מדוע חשוב שמערכת ההצפנה תהיה עמידה כנגד התקפת מוצפן נבחר.
השערת RSA החזקה

באריץ' ופיצמן ואחרים המציאו ב-1997 את השערת RSA החזקה (Strong RSA Assumption) שמאז מהווה בסיס למספר מערכות הצפנה וחתימה דיגיטלית בין היתר חתימה דיגיטלית של קריימר ושופ. השערה זו שונה מההשערה הרגילה בכך שהתוקף יכול לבחור גם את המפתח הציבורי, כדלהלן:
כלומר היריב מקבל מודולוס וטקסט מוצפן ועליו למצוא כל מעריך ובסיס כך שהמשוואה האמורה תתקיים. ייתכן שמשימה זו תהיה קלה יותר מפתרון בעיית RSA הרגילה ולכן ההשערה נקראת חזקה במובן הזה, שאם היא קשה, הרי שהיא משיגה ביטחון גבוה יותר מ-RSA הרגיל.
סיבית קשה ב-RSA

אף על פי ש-RSA בטוח בהנחה שהשערת RSA נכונה ובהנחה שפירוק לגורמים היא משימה קשה. בכל זאת בתנאים מסוימים RSA מדליף מעט מידע על הטקסט המקורי, כלומר קל לנחש סיביות מסוימות של המסר המקורי מתוך הטקסט המוצפן. גולדווסר ומיקאלי הראו שאם היריב יכול לנחש את הסיבית הכי פחות משמעותית של הטקסט המקורי, הוא יכול עם מידע זה לבצע התקפה שבה יצליח יחלץ את כל סיביות המקור בזמן פולינומי. ואזירני וכן שור, גולדרייך, אלקסי פישלין, שנור ואחרים הוכיחו ש- {\text{log}}({\text{log}}(n)) הסיביות הפחות משמעותיות של הטקסט המוצפן של הצפנת RSA בטוחות, דהיינו ההסתברות לניחוש מוצלח שלהן הוא לא יותר מאשר  1/2+\epsilon  כאשר  \epsilon =1/{\text{poly}}({\text{log}}(n)).
הוסטד ונוסלנד הוכיחו שכל סיביות הטקסט המקורי "מוסתרות היטב" בהצפנת RSA במובן שאם יהיה בידי תוקף יתרון כלשהו לגלות חלק מהן הרי שהוא יצליח לחשוף את כולן באותה מידה. ההוכחות מתבססות על רדוקציה המוכיחה שאם קיים אלגוריתם יעיל לניחוש סיבית אחת או יותר אפשר לבנות ממנו אלגוריתם לניחוש כל הסיביות ומכאן להיפוך פונקציית RSA.
תכונה זו היא חרב פיפיות, מצד אחד מבטיחה כי כל הסיביות מוגנות במידה שווה, אולם מצד שני מעניקה לתוקף כלי רב עוצמה, אם יעלה בידו לנחש סיבית אחת הוא יכול לגלות את כולן. מסיבה זו יישום RSA דורש תשומת לב רבה וזהירות שלא ייוצר מצב שחלק מהמערכת ידליף שלא במודע רסיס כלשהו שיאפשר לתוקף לשבור את המערכת כולה.
התקפת מוצפן נבחר

התקפת מוצפן נבחר על RSA מוגדרת כדלהלן: לתוקף גישה לאורקל אשר מבצע עבורו עם מפתח הצפנה זהה,  k פענוחים של  k טקסטים מוצפנים  c_{1},c_{2},...,c_{k} (לא בהכרח קשורים זה בזה) ומתוך מידע זה עליו לגלות  C אחר שאינו נמנה כמובן עליהם. ההתקפה מתחלקת לשני סוגים CCA1 ו-CCA2 כאשר השנייה מאפשרת שיהיה קשר בין  C שאותו התוקף מעוניין לגלות לבין הפענוחים שקיבל, במילים אחרות הוא יכול לבחור את הפענוחים שברצונו לקבל לפי  C בהתאם לתוצאות קודמות כלשהן.
היות שפונקציית RSA דטרמיניסטית באופיה לא ניתן לסכל התקפה זו. הדרך היחידה לסכלה היא לעשות שימוש בסכימת ריפוד אקראית על המסר לפני ההצפנה כמו OAEP. בצורה זו מבטלים את דטרמיניסטיות ההצפנה וההתקפה נעשית חסרת תועלת.
התקפת תיזמון

RSA הבסיסי פגיע להתקפת ערוץ צדדי המודדת במדויק את הזמן הדרוש לביצוע פענוח. למשל בהינתן כרטיס חכם שבו מוטמע מפתח הצפנה סודי שכמובן לא ניתן לראות באמצעים רגילים. בגלל שהמספרים העצומים לא מאפשרים חישוב ישיר של העלאה בחזקה פעולת הפענוח מנצלת את "אלגוריתם ריבוע וכפל" כדי לחשב את  C בחזקת  d ברקורסיה של העלאות בריבוע. העיקרון הוא להקצות משתנה זמני שמתחיל ב-1, סורקים את הייצוג הבינארי של המעריך מימין לשמאל (מהסיבית הכי פחות משמעותית לסיבית העליונה). אם הסיבית היא "1" מכפילים את המשתנה הזמני ב- C ומעלים בריבוע ואילו אם הסיבית היא "0" מבצעים רק העלאה בריבוע, מצמצמים את התוצאה במודולוס וממשיכים כאשר התוצאה האחרונה היא במשתנה הזמני. היות ש- d אי זוגי, אנחנו יודעים שבסבב הראשון מתבצעת העלאה בריבוע וכפל מלא ב- C אם מודדים את הזמן הדרוש לפעולה זו ומשווים עם הפעולה של האלגוריתם בסבב הבא ונמצא הבדל אפילו כלשהו אפשר להעריך שהסיבית השנייה היא "0". בדרך זו ניתן לעלות על כל הסיביות. באותה מידה אפשר לבצע את ההתקפה על ידי מדידת הפרשי צריכת החשמל בזמן ביצוע פעולות ההעלאה בריבוע וכפל.
דרך אחת לסכל התקפה זו היא באמצעות טכניקת "סינוור" (blinding) המנצלת את תכונת ההומומורפיות של RSA. לפני הפענוח מכפילים את המסר במספר אקראי כלשהו ולאחר הפענוח מחלקים בו שוב. בדרך זו מדידת התזמון אינה מועילה לתוקף כי המסר אקראי.
מחשב קוונטי ובעיית RSA

היות שביטחון הצפנת RSA מבוסס בעיקר על פירוק לגורמים - בידיעת הגורמים הראשוניים של המודולוס השיטה הופכת ללא בטוחה כלל, יש חשיבות בהקשר זה להתקדמות הטכנולוגית בכל המישורים בתחום פירוק לגורמים. מסיבה זו עם המצאת אלגוריתם שור והדיון על מחשבים קוונטיים, הנושא נעשה רגיש. כאשר מחשב קוונטי פונקציונלי יהפוך למעשי רוב האלגוריתמים האסימטריים ביניהם RSA יצאו מכלל שימוש.
ב-2011 פרסמה חברת D-Wave הקנדית שהצליחה לייצר מעבד קוונטי המכיל 128 קיוביטים שנועד בעיקר לפתרון בעיות כמו אופטימיזציה, מדגמים, ביואינפורמטיקה וכדומה. מומחי החברה הדגישו שהמעבד אינו מסוג מעבד לשימוש כללי ולכן לא מתאים לכל מטרה ועוד הם מצפים לכל היותר לשיפור ריבועי ביכולת החישובית לעומת מחשב קונבנציונלי בפתרון בעיות מסוימות בתורת המספרים. במאי 2013 הכריזה החברה על מחשב קוונטי מדור שני בעל 512 קיוביטים. המעבד של D-Wave כפי שהוצג אינו מתאים לפירוק לגורמים משום שלא ניתן להריץ עליו את אלגוריתם שור. המחשבים הקוונטיים הדיגיטליים שפותחו נכון להיות אינם מסוגלים לפרק לגורמים מספרים גדולים לפי התקן העולמי הנוכחי. בנוסף כל מספר שניתן לטעון ב-512 קיוביטים אפשר לפרק לגורמים על מחשב קונבנציונלי.
ראו גם

RSA
הצפנת פאיי
הצפנת קריימר-שופ
הצפנת רבין
התקפת שיבוש (קריפטוגרפיה)
הערות שוליים

↑  D. Boneh and R. Venkatesan. Breaking RSA may not be equivalent to factoring. In EURO-CRYPT '98, volume 1403 of Lecture Notes in Computer Science, pages 59-71. Springer-Verlag,1998.
↑  C. Pomerance. A tale of two sieves. Notices Amer. Math. Soc., 43:1473-1485, 1996.
↑  A. K. Lenstra and H. W. Lenstra, Jr. Algorithms in number theory. In Handbook of Theoretical Computer Science (Volume A: Algorithms and Complexity), chapter 12, pages 673-715. Elsevier and MIT Press, 1990.
↑  The RSA Factoring Challenge
↑  http://eprint.iacr.org/2010/006.pdf
↑  http://tau.ac.il/~tromer/papers/cbtwirl.pdf
↑  Robert Graham, Tor is still DHE 1024 (NSA crackable) (באנגלית)
↑  M. Wiener. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36:553-558, 1990.
↑  D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 10:233-260, 1997.
↑  J. Hastad. Solving simultaneous modular equations of low degree. SIAM J. of Computing,
↑  D. Coppersmith, M. Franklin, J. Patarin, and M. Reiter. Low-exponent RSA with related messages. In EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 1-9. Springer-Verlag, 1996.
↑  D. Boneh, G. Durfee, and Y. Frankel. An attack on RSA given a fraction of the private key bits. In AsiaCrypt '98, volume 1514 of Lecture Notes in Computer Science, pages 25-34. Springer-Verlag, 1998.
↑  Niko Baric and Birgit Pfitzmann. Collision-free accumulators and failstop signature schemes without trees. In Advances in Cryptology - EUROCRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 480–494. Springer-Verlag, 1997.
↑  S. Goldwasser, S. Micali, and P. Tong. Why and how to establish a private code on a public network. In Proc. FOCS ’82, pages 134–144, Chicago, 1982. IEEE.
↑  Umesh Vazirani and Vijay Vazirani. RSA bits are .732 + e secure. In D. Chaum, editor, Proc. CRYPTO ’83, pages 369–375. Plenum Press, 1984.
↑  W. B. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr. RSA/Rabin functions: certain parts are as hard as the whole. SIAM J. Computing, 17(2):194–209, April 1988.
↑  Johan Hastad and Mats Naslund. The security of individual RSA bits. In IEEE Symposium on Foundations of Computer Science, pages 510–521, 1998.
אוטווה פיורי

אוטווה פיורי היה מועדון כדורגל קנדי ששיחק בליגת ה-NASL. המועדון הוקם ב-2011, וקיבל את שמו ב-26 בפברואר 2013 והצטרפף ל-NASL ולקנדיאן צ'מפיונשיפ ב-2014. משחקם הראשון היה משחק נגד ניו יורק קוסמוס ב-20 ביולי 2014. ב-8 בנובמבר 2019 המועדון פורק.
היסטוריה

ב-20 ביוני 2011 NASL הודיעה כי הקבוצה "אוטווה פיורי" תצטרף לליגה בשנת 2014 לאחר סיום העבודת באצטדיונה הביתי. קבוצת ספורט ובידור אוטווה (OSEG) היא בעלי הקבוצה. הקבוצה החליפה את הקבוצה אוטווה פיורי ס.צ, ששיחקה בליגת ה-USL בשנת 2014. גם קבוצת הנשים של המועדון הקודם התפרקה בשנת 2014 ושרידיה עברו למועדון החדש. הקבוצה הודיעה ב-15 בדצמבר 2014 שתשחק בעונה הבאה בליגת הפרמייר ליג של קוויבק. בעונת 2015 זכתה הקבוצה באליפות הסתיו של ליגת ה-NASL. בתום העונה סיימה הקבוצה במקום השני לאחר שהפסידה לניו יורק קוסמוס בגמר הפלייאוף.
בעונת 2017 הצטרפה הקבוצה לליגת ה-USL. בנובמבר 2019 הודיעה על הפסקה פעילותה.
אצטדיון

אצטדיון קית האריס, אוטווה, אונטריו (2014)
אצטדיון טי די פלייס, אוטווה, אונטריו (2014–2019)
תחילה שיחק המועדון באצטדיונה של אוניברסיטת קרלטון עד להכשרת אצטדיון טי די פלייס למשחקי ה-NASL.
הערות שוליים

↑  אתר הליגה
↑  אתר הקבוצה
↑  אתר חדשות
↑  אתר הליגה
↑  Way machine
↑  אתר הקבוצה
שיחת דקלים

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

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

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