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

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

תיאור כללי

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

${\displaystyle E(m_{0},r_{0})E(m_{1},r_{1}){\text{ mod }}n=E(m_{0}+m_{1},r_{3})}$ אם ${\displaystyle m_{0}+m_{1}<p}$.

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

פונקציה לוגריתמית

נתונה החבורה ${\displaystyle \mathbb {Z} _{n}}$ (כאשר ${\displaystyle n=p^{2}q}$ וכן ${\displaystyle p}$ ו-${\displaystyle q}$ ראשוניים), הפונקציה הלוגריתמית ${\displaystyle L}$ מוגדרת מעל ${\displaystyle p}$-סילו - תת-חבורה של החבורה הכפלית ${\displaystyle \mathbb {Z} _{p^{2}}^{*}}$. אם נתון ראשוני ${\displaystyle p}$ הקבוצה:

${\displaystyle \Gamma =\{x\in \mathbb {Z} _{p^{2}}^{*}|x\equiv 1{\text{ (mod }}p)\}}$.

היא חבורה ציקלית מסדר ${\displaystyle p(p-1)}$ לכן ${\displaystyle \#\Gamma =p}$. הפונקציה ${\displaystyle L}$ עבור ${\displaystyle x\in \Gamma }$ קלה לחישוב והיא:

${\displaystyle L(x)={\frac {x-1}{p}}}$.

והיא מוגדרת היטב. הפונקציה ${\displaystyle L(x)}$ נקראת "פונקציה לוגריתמית" של ${\displaystyle \Gamma }$ והביטוי שקול ל-${\displaystyle \log(x)}$ מעל ${\displaystyle \mathbb {Z} _{p^{2}}^{*}}$ מודולו ${\displaystyle p}$. היא הומומורפית ביחס לפעולות הכפל והחיבור כי:

${\displaystyle \forall x,y\in \Gamma \ \ \log(xy{\text{ mod }}p^{2})=\log(x)+\log(y){\text{ mod }}p}$

ולכן מתקיים:

${\displaystyle \forall g\in \Gamma ,m\in \mathbb {Z} _{p}\ \ \log(g^{m}{\text{ mod }}p^{2})=m\cdot \log(g){\text{ mod }}p}$

ההוכחה במאמר המקורי.

הצפנה ופענוח

הכנה

יהי ${\displaystyle k}$ פרמטר ביטחון (למשל ${\displaystyle k=682}$), בוחרים שני ראשוניים אקראיים ${\displaystyle p}$ ו-${\displaystyle q}$ כאשר ${\displaystyle |p|=|q|=k}$ ומחשבים את ${\displaystyle n=p^{2}q}$. בוחרים אלמנט אקראי ${\displaystyle g\in _{R}\mathbb {Z} _{n}^{*}}$ כך שהסדר של ${\displaystyle g_{p}=g^{p-1}{\text{ mod }}p^{2}}$ הוא ${\displaystyle p}$. לא קשה למצוא איבר כזה כי ${\displaystyle {\text{gcd}}(p,q-1)=1}$ וכן ${\displaystyle {\text{gcd}}(q,p-1)=1}$ כאשר gcd היא פונקציית מחלק משותף מקסימלי (לכן כל מה שצריך זה לוודא ש-${\displaystyle g_{p}\neq 1}$). מחשבים את ${\displaystyle h=g^{n}{\text{ mod }}n}$.

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

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

הצפנה

בהינתן טקסט גלוי ${\displaystyle m}$ באורך ${\displaystyle k-1}$ סיביות לכל היותר. בוחרים שלם אקראי ${\displaystyle r\in _{R}\mathbb {Z} _{n}}$ ומחשבים את:

${\displaystyle c=g^{m}h^{r}{\text{ mod }}n}$.

פענוח

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

${\displaystyle m={\frac {L(c_{p})}{L(g_{p})}}{\text{ mod }}p}$

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

${\displaystyle m=\log(c_{p})\cdot \log(g_{p})^{-1}{\text{ mod }}p}$

זה נכון כי לפי חוקי הלוגריתמים ${\displaystyle \log(x)/\log(g)}$ הוא במובן מסוים הלוגריתם של ${\displaystyle x}$ בבסיס ${\displaystyle g}$, לפי זה אם נתון:

${\displaystyle (g^{m}h^{r})^{p-1}\equiv (g^{m}g^{nr})^{p-1}\equiv (g^{p-1})^{m}{\text{ (mod }}p^{2})}$

כל מה שצריך כדי לחלץ את ${\displaystyle m}$ זה לקחת לוגריתם בבסיס ${\displaystyle g^{p-1}}$. את זה אפשר לעשות על ידי ${\displaystyle \textstyle m={\frac {\log((g^{p-1})^{m})}{\log(g^{p-1})}}}$ מודולו ${\displaystyle p}$.

ביטחון

יהי ${\displaystyle {\mathcal {G}}_{1}}$ מייצר ${\displaystyle {\mathcal {G}}_{1}(1^{k})\rightarrow n,n=p^{2}q,|p|=|q|=k}$ כאשר ${\displaystyle p}$ ו-${\displaystyle q}$ ראשוניים. בעיית הפירוק בהינתן ${\displaystyle (n,k)}$ למצוא את ${\displaystyle (p,q)}$ קשה אם עבור כל אלגוריתם פולינומי הסתברותי ${\displaystyle {\mathcal {A}}}$ ועבור כל קבוע ${\displaystyle c}$ עם ${\displaystyle k}$ גדול מספיק מתקיים:

${\displaystyle \Pr[{\mathcal {A}}(1^{k},n)=(p,q)]<1/k^{c}}$.

כמו כן בהינתן מייצר ${\displaystyle {\mathcal {G}}_{2}(1^{k})\rightarrow (n,g,c)}$ ו-${\displaystyle (n,g,k)}$ מפתח ציבורי, ${\displaystyle c}$ הטקסט המוצפן, היפוך הפונקציה קשה אם עבור כל אלגוריתם פולינומי הסתברותי ${\displaystyle {\mathcal {A}}}$ ועבור כל קבוע ${\displaystyle c}$ עם ${\displaystyle k}$ גדול מספיק מתקיים:

${\displaystyle \Pr[{\mathcal {A}}(1^{k},n,g,c)=m]<1/k^{c}}$.

קיימת הוכחה ששתי הבעיות המתוארות שקולות. אם מצליחים להפוך את פונקציית ההצפנה אז אפשר לפרק את ${\displaystyle n}$ לגורמים. בכך מוכיחים שההצפנה בטוחה בהנחה שבעיית פירוק לגורמים קשה. בדומה לבעיית השארית הריבועית, מסתמכים על העובדה שקשה להכריע האם איבר ${\displaystyle x\in \mathbb {Z} _{n}^{*}}$ הוא בתת-חבורה מסדר ${\displaystyle p}$ ומזה נובע שהטקסט המוצפן כולו בטוח סמנטית.

דוגמה במספרים קטנים

נניח שנבחרו הפרמטרים הבאים: ${\displaystyle p=107,q=89,n=p^{2}q=1018961}$.

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

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

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

הלוגריתמים של ${\displaystyle c_{p}}$ ושל ${\displaystyle g_{p}}$ (מודולו ${\displaystyle p}$) הם: ${\displaystyle \log(10594)=10593/107=99}$ וכן ${\displaystyle \log(5030)=5029/107=47}$

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

שיפורים

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

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

${\displaystyle c_{p}=c^{t}{\text{ mod }}p^{2}=g^{m(p-1)}h^{nr(p-1)}=g_{p}^{m}{\text{ mod }}p^{2}}$ ${\displaystyle m=\log(c_{p})\cdot \log(g_{p})^{-1}{\text{ mod }}p}$

הסיבוכיות השתפרה כי ${\displaystyle t}$ קטן מ-${\displaystyle p}$.

EPOC

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

הצפנה	פענוח
${\displaystyle \sigma \leftarrow _{R}\{0,1\}^{k}}$ ${\displaystyle r_{1}=H(\sigma ,m)}$ ${\displaystyle r_{2}=G(\sigma )}$ ${\displaystyle c_{1}={\text{ENC}}\_{\text{ASYM}}_{pk}(\sigma ,r_{1})}$ ${\displaystyle c_{2}={\text{ENC}}\_{\text{SYM}}_{r_{2}}(m)}$ ‎ ${\displaystyle {\text{return }}(c_{1},c_{2})}$	${\displaystyle \sigma ={\text{DEC}}\_{\text{ASYM}}_{sk}(c_{1})}$ ${\displaystyle r_{2}=G(\sigma )}$ ${\displaystyle m={\text{DEC}}\_{\text{SYM}}_{r_{2}}(c_{2})}$ ${\displaystyle r_{1}=H(\sigma ,m)}$ ${\displaystyle {\text{If }}c_{1}={\text{ENC}}\_{\text{ASYM}}_{pk}(\sigma ,r_{1}){\text{ then:}}}$ ${\displaystyle \ \ \ \ {\text{return }}m}$ ${\displaystyle {\text{else return }}\bot }$

הביטוי ${\displaystyle \leftarrow _{R}}$ פירושו בחירה של ערך אקראי בהתפלגות אחידה. הסימן ${\displaystyle \bot }$ מייצג הודעת שגיאה.

ראו גם

• הצפנת מפתח ציבורי
• ביטחון סמנטי
• הצפנת פליאיי

הערות שוליים

1. A new public-key cryptosystem as secure as factoring, Tatsuaki OkamotoShigenori Uchiyama, Advances in Cryptology - EUROCRYPT'98. Lecture Notes in Computer Science. 1403. Springer. pp. 308-318
2. Accelerating Okamoto-Uchiyama public-key cryptosystem, J.-S. Coron ; D. Naccache ; P. Paillier, 1999
3. EPOC: Efficient Probabilistic Public-Key Encryption
4. Secure Integration of Asymmetric and Symmetric Encryption Schemes, Fujisaki, E. & Okamoto, T. J Cryptol (2013)