11.25.2022

Криптосистема с открытым ключом

Пусть функция $f : A \to B$ и выполнены следующие условия:
1. Вычисление значения $b = f(a)$ для любого а из $А$ – выполняется достаточно просто
2. Нахождение значения $а$ при $b = f(a)$ достаточно трудная задача
3. $f$ – биекция

Тогда $f$ называется односторонней функцией

Для системы шифрования с открытым ключом необходимо выполнение ещё одного свойства (условия)

1. Существует такой секрет  при знании которого нахождение a из уравнения $f(a) = b$ становится достаточно простой задачей

Функцию удовлетворяющую условиям 1-4 называют односторонней функцией с секретом

Криптосистема шифрования с открытым ключом позволяет передавать сообщения секретные сообщения от одного корреспондента к другому без предварительного обмена секретных данных

Криптосистема RSA

1. Вначале выбирается два достаточно больших простых числа $p$ и $q$ и вычисляется модуль $n = p * q$. Числа $p$ и $q$ сверхсекретно, модуль $n$ – открытое.
2. Далее вычисляется функция Эйлера $f(n) = (p-1)(q-1)$, выбирается число е такое, что $\text{НОД} (е, f(n)) = 1$.

3. Параметр е служит открытым ключом шифрования. Значение  $f(n)$ держится в секрете. Из того что $\text{НОД}(e, f(n)) = 1$, можно однозначно вычислить число $d$, такое, что
   $$e * d = 1 (\text{mod } f(n)) (1 <= d <= f(n))$$
   То есть $d$ – открытый элемент к $е$ в группе $Z*f(n)$ значение $d$ является секретным ключом дешифрования.

4. В качестве платформы для единиц исходного текста выберет $Z_{n}$. Единицами шифрованного текста также будут элементы $Z_{n}$.

Единицы шифротекста (обозначаем обычно $C$) получается из единиц исходного текста m по следующему правилу: 
$С=me(\text{mod } n)$
$C$ записывается стандартным именем, т.е. $0\leq c\leq n-1$

1. Дешифрование производится следующим образом: 
   $m=(me)d(\text{mod } n)$
   Пусть $\text{НОД }(m,n)=1$. Тогда $m\in Z_{n}^{*}$, и $|Z_{n}^{*}|=(n)$. По теореме Эйлера $m^{\phi(n)}=1$. Равенство
   $$ed=1(\text{mod } (\phi(n))) \iff \exists kZ:ed=1+(n)k$$ Вычисляем:
   $$c^{d}=(m^{e})^{d}=m^{ed}=nm^{\phi(n)k}=$$
   $$=m(m^{\phi(n)^k})=m*1^k=m(\text{mod } n)$$

$\text{НОД }(m,n)=1$ является необходимым условием при RSA во многих книгах, но утверждается, что $m=m^{ed}(\text{mod } n) \forall m$

Идентификация и аутентификация

Определение: аутентификацией называется процедура, с помощью которой проверяющий устанавливает законность идентификации пользователя в информационной системе.

Результатом аутентификации является принятие или отклонение поступившего от пользователя требования.

Требования к протоколу аутентификации
1. Пользователь должен иметь возможность доказать законность своей идентификации, а проверяющий должен иметь возможность проверить это;
2. Вероятность отклонения правильного доказательства и вероятность принятия неправильного должны быть пренебрежимо малы
3. Процедура аутентификации должна быть устойчива к подбору и подделке.

Идентификация базируется на одном из следующих признаков или их комбинации:
1. Знание его-либо (пароля, pin, доказательство некоторого результата и т.д.);
2. Возможность предъявления чего-либо (смарт-карты, паспорт и т.д.);
3. Возможность проверки индивидуальных особенностей (отпечатки пальцев, подписи, голоса и т.д.)

Различают сильную и слабую аутентификацию. Пароль и pin - примеры слабой аутентификации.

В UNIX
(короче говоря в файле хранится хеш пароля)
Файл паролей содержит одностороннюю функцию, хранит образ при этой функции известного текста, а сам пароль используется как ключ для этой функции

При вводе пользователем пароля система генерирует на его основе ключ шифрования и шифрует известный текст, а затем сравнивает шифровку с первоначальной шифровкой, полученной в момент образования пароля. 

PIN, используется как фиксированный пароль, обычно совместно с каким-либо физическим носителем. PIN обычно короткий. Поэтому применяется дополнительные средства защиты.

Passkey называется технология, при которой пароль пользователя перерабатывается односторонней функцией в ключ шифрования. 

Одноразовые пароли - имеется общий список допустимых пар паролей. Пользователь выбирает одну из пар и сообщает системе. А система понимает, что правильный пароль - это второй элемент пары. Каждая пара используется только один раз.

Доказательства с нулевым разглашением

Свойства нулевого разглашения означает, что пользователь доказывает знание чего-либо таким образом, что по доказательству невозможно установить само знание.

Протокол Фиата-Шамира
1 - Какой-то центр T, которому доверяют все пользователи, выбирают открытый модуль n=pq, равный произведению различных больших секретных простых чисел p,q. Произвольный пользователь A выбирает секретное число 1sn-1, взаимно просто с n: НОД(s,n)=1. Далее A вычисляет v=s2(mod n) и регистрирует v в центре T в качестве открытого данного. 
2 - Проводится трехшаговый интерактивный процесс, в результате которого пользователь A идентифицирует себя для пользователя B, доказывая знание S. Далее приводятся передаваемые данные.

2.1 - $A$ выбирает случайное число $r$, вычисляет его квадрат
$$x=r^2(\text{mod }n)$$
и передает $x$ для $B$

2.2 - $B$ случайным образом выбирает число $e \in \{0,1\}$ и передает его $A$
3 - $A$ вычисляет $y=rs^e(\text{mod }n)$ и передает его $B$.
4 - Если $e=0$, то $y=r(\text{mod }n)$. В этом случае проверку дает равенство
$$y^2=r^2=x=x*v^0$$ Если $e=1$, то $y=rs(\text{mod }n)$, тогда
$$y^2=r^2s^2=xv(\text{mod }n)$$ что приводит к правильному выводу.

Криптостойкость этого протокола основывается на трудности вычисления квадратных корней из произвольных элементов $Z_{n}$, где $n=pq$ - произведение различных больших простых секретных чисел.

Допустим $A$ подменили некоторым $C$. При этом $S$ ему неизвестен. Может ли он обмануть $B$? Ответ - может, если угадает случайный ответ $e$.

Т.е. обмануть можно с вероятность ½. 

Поэтому протокол проводится в $t$ раундов и тогда вероятность обмана будет $\frac{1}{2t}$. При достаточно большом t вероятность угадать будет мала.