WikiSort.ru - Не сортированное

Шифрование

Задано сообщение ${\displaystyle m=(\lambda _{1},...,\lambda _{n})}$ , искажение ${\displaystyle e}$ , открытый ключ ${\displaystyle B'}$ :

${\displaystyle v=\sum \lambda _{i}b_{i}'}$

В матричном виде:

${\displaystyle v=m\cdot B'}$ .

${\displaystyle m}$ состоит из целых значений, ${\displaystyle b'}$ точка решётки, и v также точка решётки. Тогда шифротекст:

${\displaystyle c=v+e=m\cdot B'+e}$

Расшифрование

Для расшифрования необходимо вычислить:

${\displaystyle c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B^{-1}=m\cdot U+e\cdot B^{-1}}$

Часть ${\displaystyle e\cdot B^{-1}}$ убирается, из соображений приближения. Сообщение:

${\displaystyle m=m\cdot U\cdot U^{-1}}$

Пример

Выберем решётку ${\displaystyle L\subset \mathbb {R} ^{2}}$ с базисом ${\displaystyle B}$ :

${\displaystyle B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}}$ and ${\displaystyle B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}}$

где

${\displaystyle U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}}$ и

${\displaystyle U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}}$

В результате:

${\displaystyle B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}}$

Пусть сообщение ${\displaystyle m=(3,-7)}$ и вектор ошибки ${\displaystyle e=(1,-1)}$ . Тогда шифротекст:

${\displaystyle c=mB'+e=(-104,-79)}$ .

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

${\displaystyle cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right)}$ .

Округление даёт ${\displaystyle (-15,-26)}$ , восстановим сообщение:

${\displaystyle m=(-15,-26)U^{-1}=(3,-7)}$ .

NTRUEncrypt — криптосистема основанная на SVP, является альтернативой RSA и ECC. В вычислении используется кольцо многочленов.