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

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

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

E(m_0,r_0)E(m_1,r_1)\text{ mod }n=E(m_0+m_1,r_3) אם m_0+m_1.


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

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

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

המפתח הציבורי הוא: (n,g,h).
המפתח הפרטי הוא: (p,q).

h ניתן לחישוב בכל שלב מתוך g ו-n והוא נועד רק להקל על החישובים בצד המצפין, אין חובה לשלוח אותו.

#### הצפנה
בהינתן טקסט גלוי m באורך k-1 סיביות לכל היותר. בוחרים שלם אקראי r\in_R\mathbb{Z}_n ומחשבים את:

:c=g^mh^r\text{ mod }n.


#### פענוח
תחילה מחשבים את c_p=c^{p-1}\text{ mod }p^2 ואז הטקסט הגלוי מתקבל על ידי

:m=\frac{L(c_p)}{L(g_p)}\text{ mod }p

דרך אחרת להציג זאת (הכפלה בהופכי כפלי במקום חילוק):

:m=\log(c_p)\cdot\log(g_p)^{-1}\text{ mod }p


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

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

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

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

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

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

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

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

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

להצפנה בוחרים שלם אקראי r ומחשבים את c=G^mH^r\text{ mod }n ואילו לפענוח מחשבים את:

הסיבוכיות השתפרה כי t קטן מ-p.

## EPOC
EPOC קיצור של Efficient Probabilistic Public Key Encryption היא מערכת הצפנה הסתברותית שפותחה ב-1999 על ידי Okamoto, Uchiyama ו-Fujisaki מ-NTT והוצעה לתקן 1363a-2004 IEEE. היא מבוססת על פונקציית OU המתוארת והיא הוכחה בטוחה סמנטית נגד תקיפת מוצפן-נבחר במסגרת מודל אורקל אקראי, כלומר היא פועלת בשילוב עם פונקציית גיבוב. הגרסה הראשונה EPOC-1 נועדה רק לשיתוף מפתח. גרסת EPOC-2 משלבת גם פד חד-פעמי/צופן סימטרי. גרסת EPOC-3 משתמשת בשתי פונקציות גיבוב H ו-G והיא מבצעת הצפנה מאומתת כדלהלן. בהינתן פרמטר ביטחון k של פונקציית הצפנה אסימטרית \text{ASYM} כמו זו המתוארת לעיל ופונקציית הצפנה סימטרית \text{SYM} כמו צופן זרם או צופן בלוקים. מכינים מפתח פרטי sk ומפתח ציבורי pk של פונקציית ההצפנה האסימטרית ומבצעים:

הביטוי \leftarrow_R פירושו בחירה של ערך אקראי בהתפלגות אחידה. הסימן \bot מייצג הודעת שגיאה.

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

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

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