הצפנת אוקמוטו-אושיאמה

בקריפטוגרפיה, הצפנת אוקמוטו-אושיאמה (באנגלית: Okamoto-Uchiyama Cryptosystem) המסומנת בקיצור OU, היא מערכת הצפנת מפתח ציבורי הומומורפית חלקית שהתגלתה ב-1998 על ידי Tatsuaki Okamoto ו-Shigenori Uchiyama מחברת ניפון טלגרף אנד טלפון (NTT). היא שונה מ-RSA ומדיפי-הלמן בכך שזאת מערכת הצפנה מוכחת כבטוחה בהנחה שפירוק לגורמים היא בעיה קשה והיא פועלת מעל חבורת אוילר <math>\mathbb{Z}_n^*</math> כאשר <math>n=p^2q</math> וכן <math>p</math> ו-<math>q</math> ראשוניים.

==תיאור כללי==
OU היא תמורה חד-כיוונית עם דלת צונחת כאשר הדלת הצונחת היא אלגוריתם יעיל לחישוב לוגריתמים בתת-חבורה ספציפית הנקראת חבורת p. החד-כיווניות שלה נובעת מבעיית פירוק לגורמים של המודולוס <math>n=p^2q</math> וכן אפשר להוכיח שהטקסט המוצפן בטוח סמנטית כולו נגד יריב פסיבי. בגלל ש-OU הסתברותית הטקסט המוצפן נראה אקראי, כי כל טקסט קריא יכול להיות מוצפן עם אותו מפתח באופן שונה בכל פעם. הביטחון הסמנטי מסתמך על הקושי שבהבחנה בין <math>E(0,r)=h^r\text{ mod }n</math> לבין <math>E(1,r')=gh^{r'}\text{ mod }n</math> כאשר <math>r</math> ו-<math>r'</math> אקראיים ובלתי תלויים ב-<math>\mathbb{Z}_n</math>. בעיה זו נחשבת לבעיה קשה והיא שקולה לבעיית השארית הריבועית וכן שארית מסדר גבוה יותר שנחשבות לבעיות קשות. שיטת OU נחשבת ליעילה יותר בהשוואה ל-RSA להצפנה של ערכים קטנים כמו מפתח הצפנה והיא הומומורפית בגלל התכונה הבאה: 
<center>
<math>E(m_0,r_0)E(m_1,r_1)\text{ mod }n=E(m_0+m_1,r_3)</math> אם <math>m_0+m_1<p</math>.
</center>

תכונה זו שימושית במקומות בהם נדרשת הצפנה אנונימית כמו בהצבעה דיגיטלית ובמטבע דיגיטלי. החסרונות של שיטת OU הם: התנפחות הטקסט המוצפן וכן העובדה שהיא אינה בטוחה נגד יריב אקטיבי לפי מודל התקפת מוצפן-נבחר. אפשר ליישם טכניקת ריפוד דומה לזו שנעשתה ב-RSA כדי לקבל ביטחון סמנטי במסגרת מודל אורקל אקראי. כמו כן שיטה זו חשילה כי זה נובע מהתכונה הייחודית שלה. לא ידוע אם הקושי שבפירוק <math>n=p^2q</math> שונה מהקושי שבפירוק <math>n=pq</math> לכן <math>n</math> יכול להיות באורך זהה בשני המקרים (למשל 2046 סיביות כאשר כל ראשוני באורך 682 סיביות).

==פונקציה לוגריתמית==
נתונה החבורה <math>\mathbb{Z}_n</math> (כאשר <math>n=p^2q</math> וכן <math>p</math> ו-<math>q</math> ראשוניים), הפונקציה הלוגריתמית <math>L</math> מוגדרת מעל <math>p</math>-סילו - תת-חבורה של החבורה הכפלית <math>\mathbb{Z}_{p^2}^*</math>. אם נתון ראשוני <math>p</math> הקבוצה:
:<math>\Gamma=\{x\in\mathbb{Z}_{p^2}^*|x\equiv 1\text{ (mod }p)\}</math>.
היא חבורה ציקלית מסדר <math>p(p-1)</math> לכן <math>\#\Gamma=p</math>. הפונקציה <math>L</math> עבור <math>x\in\Gamma</math> קלה לחישוב והיא: 
:<math>L(x)=\frac{x-1}{p}</math>.
והיא מוגדרת היטב. הפונקציה <math>L(x)</math> נקראת "פונקציה לוגריתמית" של <math>\Gamma</math> והביטוי שקול ל-<math>\log(x)</math> מעל <math>\mathbb{Z}_{p^2}^*</math> מודולו <math>p</math>. היא הומומורפית ביחס לפעולות הכפל והחיבור כי:
:<math>\forall x,y\in\Gamma \ \ \log(xy\text{ mod }p^2)=\log(x)+\log(y)\text{ mod }p</math>
ולכן מתקיים:
:<math>\forall g\in \Gamma, m\in\mathbb{Z}_p \ \ \log(g^m\text{ mod }p^2)=m\cdot\log(g)\text{ mod }p</math>
ההוכחה במאמר המקורי.

==הצפנה ופענוח==
====הכנה====
יהי <math>k</math> פרמטר ביטחון (למשל <math>k=682</math>), בוחרים שני ראשוניים אקראיים <math>p</math> ו-<math>q</math> כאשר <math>|p|=|q|=k</math> ומחשבים את <math>n=p^2q</math>. בוחרים אלמנט אקראי <math>g\in_R\mathbb{Z}_n^*</math> כך שהסדר של <math>g_p=g^{p-1}\text{ mod }p^2</math> הוא <math>p</math>. לא קשה למצוא איבר כזה כי <math>\text{gcd}(p,q-1)=1</math> וכן <math>\text{gcd}(q,p-1)=1</math> כאשר gcd היא פונקציית מחלק משותף מקסימלי (לכן כל מה שצריך זה לוודא ש-<math>g_p\ne 1</math>). מחשבים את <math>h=g^n\text{ mod }n</math>.

המפתח הציבורי הוא: <math>(n,g,h)</math>.
המפתח הפרטי הוא: <math>(p,q)</math>.
 
<math>h</math> ניתן לחישוב בכל שלב מתוך <math>g</math> ו-<math>n</math> והוא נועד רק להקל על החישובים בצד המצפין, אין חובה לשלוח אותו.

====הצפנה====
בהינתן טקסט גלוי <math>m</math> באורך <math>k-1</math> סיביות לכל היותר. בוחרים שלם אקראי <math>r\in_R\mathbb{Z}_n</math> ומחשבים את:
<center>
:<math>c=g^mh^r\text{ mod }n</math>.
</center>

====פענוח====
תחילה מחשבים את <math>c_p=c^{p-1}\text{ mod }p^2</math> ואז הטקסט הגלוי מתקבל על ידי 
<center>
:<math>m=\frac{L(c_p)}{L(g_p)}\text{ mod }p</math>
</center>
דרך אחרת להציג זאת (הכפלה בהופכי כפלי במקום חילוק):
<center>
:<math>m=\log(c_p)\cdot\log(g_p)^{-1}\text{ mod }p</math>
</center>

זה נכון כי לפי חוקי הלוגריתמים <math>\log(x)/\log(g)</math> הוא במובן מסוים הלוגריתם של <math>x</math> בבסיס <math>g</math>, לפי זה אם נתון:
:<math>(g^mh^r)^{p-1}\equiv (g^mg^{nr})^{p-1}\equiv (g^{p-1})^m\text{ (mod }p^2)</math>
כל מה שצריך כדי לחלץ את <math>m</math> זה לקחת לוגריתם בבסיס <math>g^{p-1}</math>. את זה אפשר לעשות על ידי <math>\textstyle m=\frac{\log((g^{p-1})^m)}{\log(g^{p-1})}</math> מודולו <math>p</math>.

==ביטחון==
יהי <math>\mathcal{G}_1</math> מייצר <math>\mathcal{G}_1(1^k)\rightarrow n,n=p^2q,|p|=|q|=k</math> כאשר <math>p</math> ו-<math>q</math> ראשוניים. בעיית הפירוק בהינתן <math>(n,k)</math> למצוא את <math>(p,q)</math> קשה אם עבור כל אלגוריתם פולינומי הסתברותי <math>\mathcal{A}</math> ועבור כל קבוע <math>c</math> עם <math>k</math> גדול מספיק מתקיים:
:<math>\Pr[\mathcal{A}(1^k,n)=(p,q)]<1/k^c</math>.
כמו כן בהינתן מייצר <math>\mathcal{G}_2(1^k)\rightarrow(n,g,c)</math> ו-<math>(n,g,k)</math> מפתח ציבורי, <math>c</math> הטקסט המוצפן, היפוך הפונקציה קשה אם עבור כל אלגוריתם פולינומי הסתברותי <math>\mathcal{A}</math> ועבור כל קבוע <math>c</math> עם <math>k</math> גדול מספיק מתקיים:
:<math>\Pr[\mathcal{A}(1^k,n,g,c)=m]<1/k^c</math>.
קיימת הוכחה ששתי הבעיות המתוארות שקולות. אם מצליחים להפוך את פונקציית ההצפנה אז אפשר לפרק את <math>n</math> לגורמים. בכך מוכיחים שההצפנה בטוחה בהנחה שבעיית פירוק לגורמים קשה. בדומה לבעיית השארית הריבועית, מסתמכים על העובדה שקשה להכריע האם איבר <math>x\in\mathbb{Z}_n^*</math> הוא בתת-חבורה מסדר <math>p</math> ומזה נובע שהטקסט המוצפן כולו בטוח סמנטית.

==דוגמה במספרים קטנים==
נניח שנבחרו הפרמטרים הבאים: <math>p=107, q=89, n=p^2q=1018961</math>. 

אם <math>g=23</math> אז <math>g_p=23^{106}\text{ mod }11449=5030</math> וכן <math>h=23^{1018961}\text{ mod }1018961=19003</math>.

אם המסר להצפנה הוא <math>m=100</math> ו-<math>r=9</math> אז מתקבל <math>c=g^mh^r=46063\cdot 764299\equiv 802287</math> מודולו <math>1018961</math>.

לפענוח קודם מחשבים את: <math>c_p=802287^{106}\text{ mod }11449\equiv 10594</math>.

הלוגריתמים של <math>c_p</math> ושל <math>g_p</math> (מודולו <math>p</math>) הם: <math>\log(10594)=10593/107=99</math> וכן <math>\log(5030)=5029/107=47</math>

ואז <math>m=\log(10594)\cdot\log(5030)^{-1}=99\cdot 47^{-1}\text{ mod }107\equiv 99\cdot 41\text{ mod }107 = 100</math>.

==שיפורים==
השלב הראשון בפענוח דורש <math>O(k^3)</math> פעולות על סיביות בגלל העלאה בחזקת <math>p-1</math>. קורון נקש ופלייר הציעו לייעל את שיטת OU כך שסיבוכיותה תהיה <math>O(k^2)</math> מבלי לאבד את השקילות לבעיית הפירוק. הם הציעו להשתמש בראשוני <math>p</math> כך של-<math>p-1</math> יש גורם ראשוני גדול <math>t</math> (באורך 160 סיביות לפחות), כלומר <math>p=tu+1</math>. כמו בגרסה המקורית, בוחרים שלם <math>g<n</math> ומחשבים את <math>g_p=g^{p-1}\text{ mod }p^2</math> כך שהסדר שלו הוא <math>p</math>. מחשבים את <math>G=g^u\text{ mod }n</math>, מגרילים את <math>h</math> ומחשבים את <math>H=h^{nu}\text{ mod }n</math>. השלישייה <math>(n,G,H)</math> היא המפתח הציבורי ואילו המפתח הפרטי הוא <math>(p,q)</math>.

להצפנה בוחרים שלם אקראי <math>r<n</math> ומחשבים את <math>c=G^mH^r\text{ mod }n</math> ואילו לפענוח מחשבים את:
{| dir="ltr"
|-
|
:<math>c_p=c^t\text{ mod }p^2=g^{m(p-1)}h^{nr(p-1)}=g_p^m\text{ mod }p^2</math>
:<math>m =\log(c_p)\cdot\log(g_p)^{-1}\text{ mod }p</math>
|}
הסיבוכיות השתפרה כי <math>t</math> קטן מ-<math>p</math>.

==EPOC==
EPOC קיצור של Efficient Probabilistic Public Key Encryption היא מערכת הצפנה הסתברותית שפותחה ב-1999 על ידי Okamoto, Uchiyama ו-Fujisaki מ-NTT והוצעה לתקן 1363a-2004 IEEE. היא מבוססת על פונקציית OU המתוארת והיא הוכחה בטוחה סמנטית נגד תקיפת מוצפן-נבחר במסגרת מודל אורקל אקראי, כלומר היא פועלת בשילוב עם פונקציית גיבוב. הגרסה הראשונה EPOC-1 נועדה רק לשיתוף מפתח. גרסת EPOC-2 משלבת גם פד חד-פעמי/צופן סימטרי. גרסת EPOC-3 משתמשת בשתי פונקציות גיבוב <math>H</math> ו-<math>G</math> והיא מבצעת הצפנה מאומתת כדלהלן. בהינתן פרמטר ביטחון <math>k</math> של פונקציית הצפנה אסימטרית <math>\text{ASYM}</math> כמו זו המתוארת לעיל ופונקציית הצפנה סימטרית <math>\text{SYM}</math> כמו צופן זרם או צופן בלוקים. מכינים מפתח פרטי <math>sk</math> ומפתח ציבורי <math>pk</math> של פונקציית ההצפנה האסימטרית ומבצעים:
{| dir = "ltr"
|-
! הצפנה !! פענוח
|-
| 
:<math>\sigma\leftarrow_R \{0,1\}^k</math>
:<math>r_1=H(\sigma,m)</math>
:<math>r_2=G(\sigma)</math>
:<math>c_1=\text{ENC}\_\text{ASYM}_{pk}(\sigma,r_1) </math>
:<math>c_2=\text{ENC}\_\text{SYM}_{r_2}(m)</math>
:
:<math>\text{return }(c_1,c_2)</math>
|| 
:<math>\sigma=\text{DEC}\_\text{ASYM}_{sk}(c_1)</math>
:<math>r_2=G(\sigma)</math>
:<math>m=\text{DEC}\_\text{SYM}_{r_2}(c_2)</math>
:<math>r_1=H(\sigma,m)</math>
:<math>\text{If }c_1 = \text{ENC}\_\text{ASYM}_{pk}(\sigma,r_1)\text{ then:}</math>
:<math>\ \ \ \ \text{return }m</math>
:<math>\text{else return }\bot</math>
|}
הביטוי <math>\leftarrow_R</math> פירושו בחירה של ערך אקראי בהתפלגות אחידה. הסימן <math>\bot</math> מייצג הודעת שגיאה.

==ראו גם==
* הצפנת מפתח ציבורי
* ביטחון סמנטי
* הצפנת פליאיי

== הערות שוליים ==

קטגוריה:הצפנה
קטגוריה:מפתח ציבורי