خوارزمية بلوم-ميكالي

خوارزمية بلوم-ميكالي هي مولد أرقام شبه عشوائية آمن تشفيرياً . تستمد الخوارزمية أمانها من صعوبة حساب اللوغاريتمات المنفصلة . ^{[ 1 ]}

يترك${\displaystyle p}$ليكن عددًا أوليًا فرديًا، وليكن${\displaystyle g}$ليكن جذرًا أوليًا modulo${\displaystyle p}$. يترك${\displaystyle x_{0}}$كن بذرة، ودع

${\displaystyle x_{i+1}=g^{x_{i}}\ {\bmod {\ p}}}$.

ال${\displaystyle i}$يكون ناتج الخوارزمية رقم 1 إذا ${\displaystyle x_{i}\leq {\frac {p-1}{2}}}$وإلا فإن الناتج يكون 0. وهذا يعادل استخدام بت واحد من${\displaystyle x_{i}}$كرقم عشوائي. وقد ثبت ذلك.${\displaystyle nc-1}$أجزاء من${\displaystyle x_{i}}$يمكن استخدام هذه الطريقة إذا كان حل مشكلة اللوغاريتم المنفصل غير ممكن حتى بالنسبة للأسس التي تحتوي على عدد قليل من القيم.${\displaystyle c}$بتات. ^{[ 2 ]}

لكي يكون هذا المولد آمنًا، يجب أن يكون العدد الأولي${\displaystyle p}$يجب أن يكون كبيرًا بما يكفي بحيث يتم حساب اللوغاريتمات المنفصلة modulo${\displaystyle p}$غير عملي. ^{[ 1 ]} بتعبير أدق، أي طريقة تتنبأ بالأرقام المُولَّدة ستؤدي إلى خوارزمية تحل مسألة اللوغاريتم المنفصل لذلك العدد الأولي. ^{[ 3 ]}

توجد ورقة بحثية تناقش أمثلة محتملة لهجوم التنازل الدائم الكمومي على بنية بلوم-ميكالي. توضح هذه الهجمات كيف يمكن توسيع نطاق هجوم سابق على مولد بلوم-ميكالي ليشمل بنية بلوم-ميكالي بأكملها، بما في ذلك مولدات بلوم بلوم شوب وكاليسكي . ^{[ 4 ]}

• https://web.archive.org/web/20080216164459/http://crypto.stanford.edu/pbc/notes/crypto/blummicali.xhtml