Русская Википедия:EPOC (схема шифрования)

EPOC (Шаблон:Lang-en; эффективное вероятностное шифрование с открытым ключом) — это вероятностная схема шифрования с открытым ключом.

EPOC был разработан в ноябре 1998 г. Т. Окамото (англ. T. Okamoto), С. Учияма (англ. S. Uchiyama) и Э. Фудзисаки (англ. E. Fujisaki) из NTT Laboratories в Японии. Он основан на модели случайного оракула, в которой функция шифрования с открытым ключом преобразуется в безопасную схему шифрования с использованием (действительно) случайной хеш-функции; результирующая схема разработана так, чтобы быть семантически защищённой от атак на основе подобранного шифротекста Шаблон:Sfn.

Виды схем

Функция шифрования EPOC — это функция OU (англ. Okamoto-Uchiyama), которую инвертировать так же сложно, как факторизировать составной целочисленный открытый ключ. Существует три версии EPOCШаблон:Sfn:

EPOC-1, использующий одностороннюю функцию(англ. trapdoor function) и случайную функцию (хеш-функцию)Шаблон:Sfn.;
EPOC-2, использующий одностороннюю функцию, две случайные функции (хеш-функции) и шифрование с симметричным ключом (например, одноразовый блокнот и блочные шифры)Шаблон:Sfn;
EPOC-3 использует одностороннюю функцию OU (англ. Okamoto-Uchiyama) и две случайные функции (хеш-функции), а также любую симметричную схему шифрования, такую как одноразовые блокноты (англ. one-time pad) или блочный шифр.

СвойстваШаблон:Sfn Шаблон:Sfn

EPOC обладает следующими свойствами:

EPOC-1 семантически безопасен, устойчив к атакам на основе подобранного шифротекста (IND-CCA2 или NM-CCA2) в модели случайного оракула Шаблон:Sfn в предположении p-подгруппы, которое вычислительно сопоставимо с предположениями квадратичного вычета и вычетов более высокой степени.
EPOC-2 с одноразовым блокнотом семантически безопасен, устойчив к атакам на основе подобранного шифротекста (IND-CCA2 или NM-CCA2) в модели случайного оракула в предположении факторизации.
EPOC-2 с симметричным шифрованием семантически безопасен, устойчив к атакам на основе подобранного шифротекста (IND-CCA2 или NM-CCA2) в модели случайного оракула в рамках предположения факторизации, если базовое симметричное шифрование является безопасным против пассивных атак (атак вида, когда криптоаналитик имеет возможность только видеть предаваемые шифротексты и генерировать собственные, используя открытый ключ.).

Предыстория

Диффи и Хеллман предложили концепцию криптосистемы с открытым ключом (или односторонней функции) в 1976 году. Хотя многое криптографы и математики провели обширные исследования, чтобы реализовать концепцию криптосистем с открытым ключом в течение более чем 20 лет, было найдено очень мало конкретных методов, которые являются безопаснымиШаблон:Sfn.

Типичным классом методов является RSA-Rabin, представляющий собой комбинацию полиномиального алгоритма нахождения корня многочлена в кольце вычетов по модулю составного числа (в конечном поле)и неразрешимой задачи факторизации(по вычислительной сложности). Другим типичным классом методов является метод Диффи-Хеллмана, Эль-Гамаля, который представляет собой комбинацию коммутативного свойства логарифма в конечной Абелевой группе и неразрешимой задачи дискретного логарифма Шаблон:Sfn.

Среди методов RSA-Rabin и Diffie-Hellman-ElGamal для реализации односторонней функции ни одна функция, кроме функции Рабина и её вариантов, таких как её версии эллиптической кривой и Уильямса, не была доказана такой же надёжной, как примитивные задачиШаблон:Sfn(например, задачи факторизации и дискретного логарифма).

Окамото и Учияма, предложили одностороннюю функцию, названную OU (англ. Okamoto-Uchiyama), которая практична, доказуемо безопасна и обладает некоторыми другими интересными свойствамиШаблон:Sfn.

Свойства функции OU Шаблон:Sfn

Вероятностная функция: это односторонняя, вероятностная функция. Пусть <math>E (m, r)</math> — зашифрованный текст открытого текста <math>m</math> со случайным <math>r</math>.
Односторонность функции: Доказано, что инвертирование функции так же трудно, как факторизация <math>n := p^2q</math>.
Семантическая стойкость: Функция семантически безопасна, если верно следующее предположение (предположение p-подгруппы): <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> \mathbf{Z}/n\mathbf{Z}</math>. Это предположение о неразличимости шифротекста для атак на основе подобранного открытого текста вычислительно сравнимо с поиском квадратичного вычета и вычета более высокой степени.
Эффективность: В среде использования криптосистем с открытым ключом, где криптосистема с открытым ключом используется только для распространения секретного ключа(например, длиной 112 и 128 бит) криптосистемы с секретным ключом(например, Triple DES и IDEA), скорость шифрования и дешифрования функции OU сравнима (в несколько раз медленнее) со скоростью криптосистем с эллиптической кривой.
Свойство гомоморфного шифрования: Функция обладает свойством гомоморфного шифрования: <math>E(m_0,r_0)E(m_1,r_1)\text{ mod }n=E(m_0+m_1,r_3),\text{ if }m_0+m_1<p</math>(Такое свойство используется для электронного голосования и других криптографических протоколов).
Неразличимость шифротекста: Даже тот, кто не знает секретного ключа, может изменить зашифрованный текст, <math>C = E(m, r)</math>, на другой зашифрованный текст, <math>C' = Ch^{r'} \text{ mod } n</math>, сохраняя при этом открытый текст m (то есть <math>C' = E(m, r)</math>), и связь между <math>C</math> и <math>C'</math> может быть скрыта (то есть <math>(C, C')</math> и <math>(C, E(m', t)</math> неразличимы). Такое свойство полезно для протоколов защиты конфиденциальности).

Доказательство безопасности схемы шифрования

Одним из важнейших свойств шифрования с открытым ключом является доказуемая безопасность. Самое сильное понятие безопасности в шифровании с открытым ключом — это понятие семантической защиты от атак на основе подобранного шифротекста.

Доказано, что семантическая защита от атак на основе адаптивно подобранного шифротекста (IND-CCA2) эквивалентна (или достаточна) самому сильному понятию безопасности (NM-CCA2)Шаблон:Sfn Шаблон:Sfn.

Фудзисаки и Окамото реализовали две общие и эффективные меры для преобразования вероятностной односторонней функции в защищённую схему IND-CCA2 в модели случайного оракула Шаблон:Sfn. Одна из них — это преобразование семантически безопасной (IND-CPA) односторонней функции в защищённую схему IND-CCA2. Другая, от односторонней функции (OW-CPA) и шифрования с симметричным ключом (включая одноразовый блокнот) до защищённой схемы IND-CCA2. Последнее преобразование может гарантировать полную безопасность системы шифрования с открытым ключом в сочетании со схемой шифрования с симметричным ключом Шаблон:Sfn.

Схема шифрования EPOC

Обзор

Схема шифрования с открытым ключом EPOC, которая задаётся триплетом <math>(\mathcal{G}, \mathcal{E}, \mathcal{D})</math>, где <math>\mathcal{G}</math>-операция генерации ключа, <math>\mathcal{E}</math>-операция шифрования и <math>\mathcal{D}</math>-операция дешифрования.

Схемы EPOC: EPOC-1 и EPOC-2.

EPOC-1 предназначен для распределения ключей, а EPOC-2 предназначен для распределения ключей и передачи зашифрованных данных, а также распределения более длинного ключа при ограниченном размере открытого ключа.

Типы ключей

Существует два типа ключей: открытый ключ OU и закрытый ключ OU, оба из которых используются в криптографических схемах шифрования EPOC-1, EPOC-2Шаблон:Sfn.

OU открытый ключШаблон:Sfn

Открытый ключ OU — это набор <math>(n, g, h, pLen)</math>, компоненты которого имеют следующие значения:

<math>n</math> — неотрицательное целое число
<math>g</math> — неотрицательное целое число
<math>h</math> — неотрицательное целое число
<math>pLen</math> — секретный параметр, неотрицательное целое число

На практике в открытом ключе OU модуль <math>n</math> принимает вид <math>n := p^2q</math>, где <math>p</math> и <math>q</math> — два различных нечётных простых числа, а битовая длина <math>p</math> и <math>q</math> равна <math>pLen</math>. <math>g</math>-элемент в <math>(\mathbf{Z}/n\mathbf{Z})^*</math> такой, что порядок <math>g_p</math> в <math>(\mathbf{Z}/p^2\mathbf{Z})^*</math> равен <math>p</math>, где <math>g_p :=g^{p-1}\text{ mod }p^2</math>. <math>h</math>-элемент в <math>(\mathbf{Z}/n\mathbf{Z})^*</math>.

OU закрытый ключШаблон:Sfn

Закрытый ключ OU — это набор <math>(p, g, pLen, w)</math>, компоненты которого имеют следующие значения:

<math>p</math> — первый фактор, неотрицательное целое число
<math>h</math> — второй фактор, неотрицательное целое число
<math>pLen</math> — секретный параметр, неотрицательное целое число
<math>w</math> — значение <math>L (g_p)</math>, где <math>L (x) =\frac{x-1}p</math>, неотрицательное целое число

EPOC-1Шаблон:Sfn

Создание Ключа: G

Ввод и вывод <math>\mathcal{G}</math> следующие:

[Входные данные]: Секретный параметр <math>k</math>(<math>= pLen</math>) — положительное целое число.

[Выходные данные]: Пара открытого ключа <math>(n, g, h, H, pLen, mLen, hLen, rLen)</math> и секретного ключа <math>(p, g_p)</math>.

Операция <math>\mathcal{G}</math> со входом <math>k</math> выглядит следующим образом:

Выберем два простых числа <math>p</math>, <math>q</math> (<math>|p| = |q| = k</math>) и вычислим <math>n := p^2q</math>. Здесь <math>p-1 = p'u</math> и <math>q-1 = q'v</math> такое, что <math>p'</math> и <math>q'</math> — простые числа, а <math>|u|</math> и <math>|v|</math> такие, что <math>O (\log k)</math>.

Выберем <math>g \in (\mathbf{Z}/n\mathbf{Z})^*</math> случайным образом так, чтобы порядок <math>g_p:=g^{p-1}\text{ mod } p^2</math> был равен <math>p</math> (Заметим, что НОД(<math>p</math>, <math>q-1</math>)<math>=1</math> и НОД(<math>q</math>, <math>p-1</math>)<math>=1</math>).

Выберем <math>h_0</math> из <math>(\mathbf{Z}/n\mathbf{Z})^*</math> случайным образом и независимо от <math>g</math>. Вычислим <math>h := h_n^0 \text{ mod } n</math>.

Установить <math>pLen:=k</math>. Установите <math>mLen</math> и <math>rLen</math> такими, что <math>mLen+rLen\leq pLen-1</math>.

Выберем хеш-функцию <math>H:\{0,1\}^*\rightarrow\{0,1\}^{hLen}</math>.

Примечание: <math>g_p</math> является дополнительным параметром, повышающим эффективность дешифрования, и может быть вычислен из <math>p</math> и <math>g</math>. <math>h=g^n\text{ mod }n</math>, когда <math>hLen = (2 + c_0)k</math> (<math>c_0</math>-константа <math>> 0</math>). <math>H</math> может быть зафиксирован системой и совместно использован многими пользователями.

Шифрование: E

Ввод и вывод <math>\mathcal{E}</math> следующие:

[Входные данные]: Открытый текст <math>M\in \{0, 1\}^{mLen}</math> вместе с открытым ключом <math>(n, g, h, H, pLen, mLen, hLen, rLen)</math>.

[Выходные данные]: Шифротекст С.

Операция <math>\mathcal{E}</math> со входами <math>M</math>, <math>(n, g, h, H, mLen, rLen)</math> выглядит следующим образом:

Выберем <math>R \in \{0, 1\}^{rLen}</math> и вычислим <math>r: = H (M\parallel R)</math>. Здесь <math>M \parallel R</math> обозначает конкатенацию <math>M</math> и <math>R</math>.

Вычислить <math>C</math>:

<math>C := g^{(M\parallel R)}h^r\text{ mod }n.</math>

Дешифрование: D

Ввод и вывод <math>\mathcal{D}</math> следующие:

[Входные данные]: Шифротекст <math>C</math> наряду с открытым ключом <math>(n, g,h,H,pLen,mLen, hLen)</math> и секретным ключом <math>(p, g_p)</math>.

[Выходные данные]: Открытый текст <math>M</math> или нулевая строка.

Операция <math>\mathcal{D}</math> со входами <math>C</math>, <math>(n, g, h, H, pLen, mLen, hLen)</math> и <math>(p, g_p)</math> выглядит следующим образом:

Вычислим <math>C_p:=C^{p-1}\text{ mod }p^2</math>, а <math>X:=\frac{L(C_p)}{L(g_p)}\text{ mod }p</math>, где <math>L(x):=\frac{x-1}p</math>.

Проверим, верно ли следующее уравнение: <math>C = g^Xh^{H(X)}\text{ mod }n</math>.

Если выражение верно, то выведем <math>[X]^{mLen}</math> как расшифрованный открытый текст, где <math>[X]^{mLen}</math> обозначает наиболее значимые <math>mLen</math> биты в <math>X</math>. В противном случае выведем нулевую строку.

EPOC-2Шаблон:Sfn Шаблон:Sfn

Создание Ключа: G

Ввод и вывод <math>\mathcal{G}</math> следующие:

[Входные данные]: Секретный параметр <math>k</math>(<math>= pLen</math>).

[Выходные данные]: Пара открытого ключа <math>(n, g, h, H, G, pLen, hLen, gLen, rLen)</math> и секретного ключа <math>(p, g_p)</math>.

Операция <math>\mathcal{G}</math> со входом <math>k</math> выглядит следующим образом:

Выберем два простых числа <math>p</math>, <math>q</math> (<math>|p| = |q| = k</math>) и вычислим <math>n := p^2q</math>. Здесь <math>p-1 = p'u</math> и <math>q-1 = q'v</math> такое, что <math>p'</math> и <math>q'</math> — простые числа, а <math>|u|</math> и <math>|v|</math> такие, что <math>O (\log k)</math>.

Выберем <math>g \in (\mathbf{Z}/n\mathbf{Z})^*</math> случайным образом так, чтобы порядок <math>g_p:=g^{p-1}\text{ mod } p^2</math> был равен <math>p</math>.

Выберем <math>h_0</math> из <math>(\mathbf{Z}/n\mathbf{Z})^*</math> случайным образом и независимо от <math>g</math>. Вычислим <math>h := h_n^0 \text{ mod } n</math>.

Установить <math>pLen:=k</math>. Установите <math>mLen</math> и <math>rLen</math> такими, что <math>mLen+rLen\leq pLen-1</math>.

Выберем хеш-функции <math>H:\{0,1\}^*\rightarrow\{0,1\}^{hLen}</math> и <math>G:{0,1}^*\rightarrow\{0,1\}^{hLen}</math>.

Примечание: <math>g_p</math> является дополнительным параметром, повышающим эффективность дешифрования, и может быть вычислено из <math>p</math> и <math>g</math>. <math>h=g^n\text{ mod }n</math>, когда <math>hLen = (2 + c_0)k</math> (<math>c_0</math>-константа <math>> 0</math>). <math>H</math> и <math>G</math> могут быть зафиксированы системой и совместно использованы многими пользователями.

Шифрование: E

Пусть <math>SymE = (SymEnc, SymDec)</math> — пара алгоритмов шифрования и дешифрования с симметричным ключом <math>K</math>, где длина <math>K</math> равна <math>gLen</math>. Алгоритм шифрования <math>SymEnc</math> принимает ключ <math>K</math> и открытый текст <math>X</math> и возвращает зашифрованный текст <math>SymEnc(K,X)</math>. Алгоритм расшифровки <math>SymDec</math> принимает ключ <math>K</math> и зашифрованный текст <math>Y</math> и возвращает открытый текст <math>SymDec(K, Y )</math>.

Ввод и вывод <math>\mathcal{E}</math> следующие:

[Входные данные]: Открытый текст <math>M \in \{0, 1\}^{mLen}</math> вместе с открытым ключом <math>(n, g, h, H, G, pLen, hLen, gLen, rLen)</math> и <math>SymEnc</math>.

[Выходные данные]: Зашифрованный текст <math>C = (C_1, C_2)</math>.

Операция <math>\mathcal{E}</math> со входами <math>M</math>, <math>(n, g, h, H, G, pLen, hLen, gLen, rLen)</math> и <math>SymEnc</math> выглядит следующим образом:

Выберем <math>r \in \{0, 1\}^{rLen}</math> и вычислим <math>G (R)</math>.

Вычислим <math>H (M\parallel R)</math>. Здесь <math>M \parallel R</math> обозначает конкатенацию <math>M</math> и <math>R</math>.

<math>C_1:=g^Rh^{H(M \parallel R)}\text{ mod }n</math>; <math>C_2:=SymEnc(G(R),M)</math>

Примечание: типичный способ реализации <math>SymE</math> — это одноразовый блокнот. То есть, <math>SymEnc(K, X) := K\oplus X</math>, и <math>SymDec(X, Y) := X\oplus Y</math> , где <math>\oplus</math> обозначает операцию побитового исключающего ИЛИ.

Дешифрование: D

Ввод и вывод <math>\mathcal{D}</math> следующие:

[Входные данные]: Шифротекст <math>C=(C_1,C_2)</math> наряду с открытым ключом <math>(n, g,h,H, G,pLen,hLen, gLen, rLen)</math>, секретным ключом <math>(p, g_p)</math> и <math>SymDec</math>.

[Выходные данные]: Открытый текст <math>M</math> или нулевая строка.

Операция <math>\mathcal{D}</math> со входами <math>C=(C_1,C_2)</math>, <math>(n, g,h,H, G,pLen,hLen, gLen)</math>, <math>(p, g_p)</math> и <math>SymDec</math> выглядит следующим образом:

Вычислим <math>C_p:=C^{p-1}\text{ mod }p^2</math>, а <math>R':=\frac{L(C_p)}{L(g_p)}\text{ mod }p</math>, где <math>L(x):=\frac{x-1}p</math>.

Вычислим <math>M':= SymDec(G(R'),C_2).</math>

Проверим, верно ли следующее уравнение: <math>C = g^{R'}h^{H(M'\parallel R')}\text{ mod }n</math>.

Если выражение верно, то выведем <math>M'</math> как расшифрованный открытый текст. В противном случае выведем нулевую строку.

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Русская Википедия:EPOC (схема шифрования)

Содержание

Виды схем

СвойстваШаблон:Sfn Шаблон:Sfn

Предыстория

Свойства функции OU Шаблон:Sfn

Доказательство безопасности схемы шифрования

Схема шифрования EPOC

Обзор

Типы ключей

OU открытый ключШаблон:Sfn

OU закрытый ключШаблон:Sfn

EPOC-1Шаблон:Sfn

Создание Ключа: G

EPOC-2Шаблон:Sfn Шаблон:Sfn

Создание Ключа: G

Примечания

Литература

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты

Русская Википедия:EPOC (схема шифрования)

Виды схем

СвойстваШаблон:SfnШаблон:Sfn

Предыстория

Свойства функции OUШаблон:Sfn

Доказательство безопасности схемы шифрования

Схема шифрования EPOC

Обзор

Типы ключей

OU открытый ключШаблон:Sfn

OU закрытый ключШаблон:Sfn

EPOC-1Шаблон:Sfn

Создание Ключа: G

EPOC-2Шаблон:SfnШаблон:Sfn

Создание Ключа: G

Примечания

Литература

Навигация

Поиск

СвойстваШаблон:Sfn Шаблон:Sfn

Свойства функции OU Шаблон:Sfn

EPOC-2Шаблон:Sfn Шаблон:Sfn