ACE Encrypt

ACE (Advanced Cryptographic Engine) — набор программных средств, реализующих шифрование в режиме схемы шифрования с открытым ключом, а также в режиме цифровой подписи. Соответствующие названия этих режимов — «ACE Encrypt» и «ACE Sign». Схемы являются вариантами реализации схем Крамера-Шоупа. Внесённые изменения нацелены на достижение наилучшего баланса между производительностью и безопасностью всей системы шифрования.

Авторы

Все алгоритмы, написанные в ACE, основаны на алгоритмах, разработанных Виктором Шоупом(Victor Shoup) и Рональдом Крамером (Ronald Cramer). Полная спецификация алгоритмов написана Виктором Шоупом. Реализация алгоритмов выполнена Томасом Швейнбергером(Thomas Schweinberger) и Медди Нассей (Mehdi Nassehi), их поддержкой и развитием занимается Виктор Шоуп. Томас Швейнберг принимал участие в составлении документа спецификаций ACE, а также написал руководство пользователя.
Рональд Крамер в настоящее время находится в университете Орхуса, Дания. Он принимал участие в работе, относящейся к ACE Encrypt пока находился в ETH в Цюрихе, Швейцария.
Медди Нассей и Томасом Швейнбергер работали над проектом ACE в исследовательской лаборатории IBM в Цюрихе, Швейцария, но в настоящее время закончили своё пребывание там.
Виктор Шоуп работает в исследовательской лаборатории IBM в Цюрихе, Швейцария.

Безопасность

Доказательство безопасности схемы шифрования и схемы цифровой подписи в ACE проводится с использованием обоснованных и естественных допущений. Четырьмя основными допущениями являются:

• Допущение Диффи-Хеллмана
• Сильное допущение RSA
• Стойкость к коллизиям на второй прообраз в SHA-1
• Псевдо-случайность режима сумматора/счётчика MARS

Основные обозначения и терминология

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

Основные математические обозначения

Z {displaystyle Z} — множество целых чисел.
F 2 [ T ] {displaystyle F_{2}[T]} — множество одномерных полиномов с коэффициентами в конечном поле F 2 {displaystyle F_{2}} с числом элементов поля — 2.
A r e m n {displaystyle Aremn} — такое целое число r ∈ { 0 , . . . , n − 1 } {displaystyle rin left{0,...,n-1 ight}} , для которого A ≡ r ( m o d n ) {displaystyle Aequiv r(modn)} при целом n > 0 {displaystyle n>0} и A ∈ Z {displaystyle Ain Z} .
A r e m f {displaystyle Aremf} — такой полином r ∈ F 2 [ T ] {displaystyle rin F_{2}[T]} с d e g ( r ) < d e g ( f ) {displaystyle deg(r)<deg(f)} , такой что A ≡ r ( m o d f ) {displaystyle Aequiv r(modf)} при A , f ∈ F 2 [ T ] , f ≠ 0 {displaystyle A,fin F_{2}[T],f eq 0} .

Основные строковые обозначения

A ∗ {displaystyle A^{ast }} — множество всевозможных строк.
A n {displaystyle A^{n}} — множество всевозможных строк длины n.
Для x ∈ A ∗ L ( x ) {displaystyle xin A^{ast }L(x)} — длина строки x {displaystyle x} . Обозначения для длины нулевой строки — λ A {displaystyle lambda _{A}} .
Для x , y ∈ A ∗ {displaystyle x,yin A^{ast }} x | | y {displaystyle x||y} — результат конкатенации строк x {displaystyle x} и y {displaystyle y} .

Биты, байты, слова

b = d e f { 0 , 1 } {displaystyle b{stackrel {mathrm {def} }{=}}left{0,1 ight}} — множество битов.
Рассмотрим множества вида b , b n 1 , ( b n 1 ) n 2 , . . . {displaystyle b,b^{n_{1}},(b^{n_{1}})^{n_{2}},...} . Для такого множества A определим нулевой элемент:

0 b = d e f 0 ∈ b {displaystyle 0_{b}{stackrel {mathrm {def} }{=}}0in b} ;
0 A n = d e f ( 0 A , . . . , 0 A ) ∈ A n {displaystyle 0_{A^{n}}{stackrel {mathrm {def} }{=}}(0_{A},...,0_{A})in A^{n}} для n > 0 {displaystyle n>0} .

Определим B = d e f b 8 {displaystyle B{stackrel {mathrm {def} }{=}}b^{8}} как множество байтов, а W = d e f b 32 {displaystyle W{stackrel {mathrm {def} }{=}}b^{32}} как множество слов.

Для x ∈ A ∗ {displaystyle xin A^{ast }} с A ∈ { b , B , W } {displaystyle Ain left{b,B,W ight}} и l > 0 {displaystyle l>0} определим оператор заполнения:

p a d l ( x ) = d e f { x , L ( x ) ≥ l x | | 0 A l − L ( x ) , L ( x ) < l {displaystyle pad_{l}(x){stackrel {mathrm {def} }{=}}{egin{cases}x,&L(x)geq lx||0_{A^{l-L(x)}},&L(x)<lend{cases}}} .

Оператор преобразования

Оператор преобразования I s r c d s t : s r c → d s t {displaystyle I_{src}^{dst}:src ightarrow dst} выполняет преобразования между элементами Z , F 2 [ T ] , b ∗ , B ∗ , W ∗ {displaystyle Z,F_{2}[T],b^{ast },B^{ast },W^{ast }} .

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

Пара ключей шифрования

В схеме шифрования ACE задействованы два типа ключей:
открытый ключ ACE: ( P , q , g 1 , g 2 , c , d , h 1 , h 2 , k 1 , k 2 ) {displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})} .
закрытый ключ ACE: ( w , x , y , z 1 , z 2 ) {displaystyle (w,x,y,z_{1},z_{2})} .
Для заданного параметра размера m {displaystyle m} , такого что 1024 ≤ m ≤ 16384 {displaystyle 1024leq mleq 16384} , компоненты ключей определяются следующим образом:
q {displaystyle q} — 256-битное простое число.
P {displaystyle P} — m-битное простое число, такое что P ≡ 1 ( m o d q ) {displaystyle Pequiv 1(modq)} .
g 1 , g 2 , c , d , h 1 , h 2 {displaystyle g_{1},g_{2},c,d,h_{1},h_{2}} — элементы { 1 , . . . , P − 1 } {displaystyle left{1,...,P-1 ight}} (чей мультипликативный порядок по модулю P {displaystyle P} делит q {displaystyle q} ).
w , x , y , z 1 , z 2 {displaystyle w,x,y,z_{1},z_{2}} — элементы { 0 , . . . , q − 1 } {displaystyle left{0,...,q-1 ight}} .
k 1 , k 2 {displaystyle k_{1},k_{2}} — элементы B ∗ {displaystyle B^{ast }} , для которых L ( k 1 ) = 20 l ′ + 64 {displaystyle L(k_{1})=20l^{prime }+64} и L ( k 2 ) = 32 ⌈ l / 16 ⌉ + 40 {displaystyle L(k_{2})=32leftlceil l/16 ight ceil +40} , где l = ⌈ m / 8 ⌉ {displaystyle l=leftlceil m/8 ight ceil } и l ′ = L b ( ⌈ ( 2 ⌈ l / 4 ⌉ + 4 ) / 16 ⌉ ) {displaystyle l^{prime }=L_{b}(leftlceil (2leftlceil l/4 ight ceil +4)/16 ight ceil )} .

Генерация ключа

Алгоритм. Генерация ключа для схемы шифрования ACE.
Вход: параметра размера m {displaystyle m} , такой что 1024 ≤ m ≤ 16384 {displaystyle 1024leq mleq 16384} .
Выход: пара открытый/закрытый ключ.

Представление шифротекста

Шифротекст в схеме шифрования ACE имеет вид

( s , u 1 , u 2 , v , e ) {displaystyle (s,u_{1},u_{2},v,e)} ,

где компоненты определяются следующим образом:
u 1 , u 2 , v {displaystyle u_{1},u_{2},v} — целые числа из { 1 , . . . , P − 1 } {displaystyle left{1,...,P-1 ight}} (чей мультипликативный порядок по модулю P {displaystyle P} делит q {displaystyle q} ).
s {displaystyle s} — элемент W 4 {displaystyle W^{4}} .
e {displaystyle e} — элемент B ∗ {displaystyle B^{ast }} .
s , u 1 , u 2 , v {displaystyle s,u_{1},u_{2},v} назовём преамбулой, а e {displaystyle e} — криптограммой. Если текст — строка из l {displaystyle l} байт, то тогда длина e {displaystyle e} равна l + 16 ⌈ l / 1024 ⌉ {displaystyle l+16leftlceil l/1024 ight ceil } .

Необходимо ввести функцию C E n c o d e {displaystyle CEncode} , которая представляет шифротекст в виде байтовой строки, а также обратную функцию C D e c o d e {displaystyle CDecode} . Для целого l > 0 {displaystyle l>0} , символьной строки s ∈ W 4 {displaystyle sin W^{4}} , целых 0 ≤ u 1 , u 2 , v < 256 l {displaystyle 0leq u_{1},u_{2},v<256^{l}} , и байтовой строки e ∈ B ∗ {displaystyle ein B^{ast }} ,

C E n c o d e ( l , s , u 1 , u 2 , v , e ) = d e f I W ∗ B ∗ ( s ) | | p a d l ( I Z B ∗ ( u 1 ) ) | | p a d l ( I Z B ∗ ( u 2 ) ) | | p a d l ( I Z B ∗ ( v ) ) | | e ∈ B ∗ {displaystyle CEncode(l,s,u_{1},u_{2},v,e){stackrel {mathrm {def} }{=}}I_{W^{ast }}^{B^{ast }}(s)||pad_{l}(I_{Z}^{B^{ast }}(u_{1}))||pad_{l}(I_{Z}^{B^{ast }}(u_{2}))||pad_{l}(I_{Z}^{B^{ast }}(v))||ein B^{ast }} .

Для целого l > 0 {displaystyle l>0} , байтовой строки ψ ∈ B ∗ {displaystyle psi in B^{ast }} , для которой L ( ψ ) ≥ 3 l + 16 {displaystyle L(psi )geq 3l+16} ,

C D e c o d e ( l , ψ ) = d e f ( I B ∗ W ∗ ( [ ψ ] 0 16 ) , I B ∗ Z ( [ ψ ] 16 16 + l ) , I B ∗ Z ( [ ψ ] 16 + l 16 + 2 l ) , I B ∗ Z ( [ ψ ] 16 + 2 l 16 + 3 l ) , [ ψ ] 16 + 3 l L ( ψ ) ) ∈ W 4 × Z × Z × Z × B ∗ {displaystyle CDecode(l,psi ){stackrel {mathrm {def} }{=}}(I_{B^{ast }}^{W^{ast }}({Bigl [}psi {Bigr ]}_{0}^{16}),I_{B^{ast }}^{Z}({Bigl [}psi {Bigr ]}_{16}^{16+l}),I_{B^{ast }}^{Z}({Bigl [}psi {Bigr ]}_{16+l}^{16+2l}),I_{B^{ast }}^{Z}({Bigl [}psi {Bigr ]}_{16+2l}^{16+3l}),{Bigl [}psi {Bigr ]}_{16+3l}^{L(psi )})in W^{4} imes Z imes Z imes Z imes B^{ast }} .

Процесс шифрования

Алгоритм. Асимметричный процесс шифрования ACE.
Вход: открытый ключ ( P , q , g 1 , g 2 , c , d , h 1 , h 2 , k 1 , k 2 ) {displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})} и байтовая строка M ∈ B ∗ {displaystyle Min B^{ast }} .
Выход: байтовая строка — шифротекст ψ   {displaystyle psi } , полученный из M {displaystyle M} .

Перед запуском процесса симметричного шифрования входное сообщение M ∈ B ∗ {displaystyle Min B^{ast }} разбивается на блоки M 1 , . . . , M t {displaystyle M_{1},...,M_{t}} , где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока E i {displaystyle E_{i}} вычисляется 16-байтовый код аутентификации. Получаем криптограмму

e = E 1 | | C 1 | | . . . | | E t | | C t {displaystyle e=E_{1}||C_{1}||...||E_{t}||C_{t}} .

L ( e ) = L ( M ) + 16 ⌈ L ( M ) / m ⌉ {displaystyle L(e)=L(M)+16leftlceil L(M)/m ight ceil } . Заметим, что если L ( M ) = 0 {displaystyle L(M)=0} , то L ( e ) = 0 {displaystyle L(e)=0} .

Алгоритм. Симметричный процесс шифрования ACE.
Вход: ( k , s , M , m ) ∈ W 8 × W 4 × Z × B ∗ {displaystyle (k,s,M,m)in W^{8} imes W^{4} imes Z imes B^{ast }} m > 0 {displaystyle m>0}
Выход: e ∈ B l {displaystyle ein B^{l}} , l = L ( M ) + 16 ⌈ L ( N ) / m ⌉ {displaystyle l=L(M)+16leftlceil L(N)/m ight ceil } .

g e n S t a t e ← I n i t G e n ( k , s ) ∈ G e n S t a t e {displaystyle genStateleftarrow InitGen(k,s)in GenState}

( k A X U , g e n S t a t e ) ← G e n W o r d s ( ( 5 L b ( ⌈ m / 64 ⌉ ) + 24 ) , g e n S t a t e ) . {displaystyle (k_{AXU},genState)leftarrow GenWords((5L_{b}(leftlceil m/64 ight ceil )+24),genState).} .

Процесс дешифрования

Алгоритм. Процесс дешифрования ACE.
Вход: открытый ключ ( P , q , g 1 , g 2 , c , d , h 1 , h 2 , k 1 , k 2 ) {displaystyle (P,q,g_{1},g_{2},c,d,h_{1},h_{2},k_{1},k_{2})} и соответствующий закрытый ключ ( w , x , y , z 1 , z 2 ) {displaystyle (w,x,y,z_{1},z_{2})} , байтовая строка ψ ∈ B ∗ {displaystyle psi in B^{ast }} .
Выход: Расшифрованное сообщение M ∈ B ∗ ∪ R e j e c t {displaystyle Min B^{ast }cup {Reject}} .

Алгоритм. Операция дешифрования S D e c {displaystyle SDec} .
Вход: ( k , s , m , e ) ∈ W 8 × W 4 × Z × B ∗ {displaystyle (k,s,m,e)in W^{8} imes W^{4} imes Z imes B^{ast }} m > 0 {displaystyle m>0}
Выход: Расшифрованное сообщение M ∈ B ∗ ∪ R e j e c t {displaystyle Min B^{ast }cup {Reject}} .

Схема цифровой подписи

В схеме цифровой подписи ACE задействованы два типа ключей:
открытый ключ цифровой подписи ACE: ( N , h , x , e ′ , k ′ , s ) {displaystyle (N,h,x,e^{prime },k^{prime },s)} .
закрытый ключ цифровой подписи ACE: ( p , q , a ) {displaystyle (p,q,a)} .
Для заданного параметра размера m {displaystyle m} , такого что 1024 ≤ m ≤ 16384 {displaystyle 1024leq mleq 16384} , компоненты ключей определяются следующим образом:
p {displaystyle p} — ⌊ m / 2 ⌋ {displaystyle leftlfloor m/2 ight floor } -битное простое число, для которого ( p − 1 ) / 2 {displaystyle (p-1)/2} — тоже простое.
q {displaystyle q} — ⌊ m / 2 ⌋ {displaystyle leftlfloor m/2 ight floor } -битное простое число, для которого ( q − 1 ) / 2 {displaystyle (q-1)/2} — тоже простое.
N {displaystyle N} — N = p q {displaystyle N=pq} и может иметь как m {displaystyle m} , так и m − 1 {displaystyle m-1} бит.
h , x {displaystyle h,x} — элементы { 1 , . . . , N − 1 } {displaystyle left{1,...,N-1 ight}} (квадратичные остатки по модулю N {displaystyle N} ).
e ′ {displaystyle e^{prime }} — 161-битное простое число.
a {displaystyle a} — элемент { 0 , . . . , ( p − 1 ) ( q − 1 ) / 4 − 1 } {displaystyle left{0,...,(p-1)(q-1)/4-1 ight}}
k ′ {displaystyle k^{prime }} — элементы B 184 {displaystyle B^{184}} .
s {displaystyle s} — элементы B 32 {displaystyle B^{32}} .

Генерация ключа

Алгоритм. Генерация ключа для схемы цифровой подписи ACE.
Вход: параметра размера m {displaystyle m} , такой что 1024 ≤ m ≤ 16384 {displaystyle 1024leq mleq 16384} .
Выход: пара открытый/закрытый ключ.

Представление подписи

Подпись в схеме цифровой подписи ACE имеет вид ( d , w , y , y ′ , k ~ ) {displaystyle (d,w,y,y^{prime },{ ilde {k}})} , где компоненты определяются следующим образом:
d {displaystyle d} — элемент B 64 {displaystyle B^{64}} .
w {displaystyle w} — целое число, такое что 2 160 ≤ w ≤ 2 161 {displaystyle 2^{160}leq wleq 2^{161}} .
y , y ′ {displaystyle y,y^{prime }} — элементы { 1 , . . . , N − 1 } {displaystyle left{1,...,N-1 ight}} .
k ~ {displaystyle { ilde {k}}} — элемент B ∗ {displaystyle B^{ast }} ;заметим, что L ( k ~ ) = 64 + 20 L B ( ⌈ ( L ( M ) + 8 ) / 64 ⌉ ) {displaystyle L({ ilde {k}})=64+20L_{B}(leftlceil (L(M)+8)/64 ight ceil )} , где M {displaystyle M} — подписываемое сообщение.

Необходимо ввести функцию S E n c o d e {displaystyle SEncode} , которая представляет подпись в виде байтовой строки, а также обратную функцию S D e c o d e {displaystyle SDecode} . Для целого l > 0 {displaystyle l>0} , байтовой строки d ∈ B 64 {displaystyle din B^{64}} , целых 0 ≤ w ≤ 256 21 {displaystyle 0leq wleq 256^{21}} и 0 ≤ y , y ′ < 256 l {displaystyle 0leq y,y^{prime }<256^{l}} , и байтовой строки k ~ ∈ B ∗ {displaystyle { ilde {k}}in B^{ast }} ,

S E n c o d e ( l , d , w , y , y ′ , k ~ ) = d e f d | | p a d 21 ( I Z B ∗ ( w ) ) | | p a d l ( I Z B ∗ ( y ) ) | | p a d l ( I Z B ∗ ( y ′ ) ) | | k ~ ∈ B ∗ {displaystyle SEncode(l,d,w,y,y^{prime },{ ilde {k}}){stackrel {mathrm {def} }{=}}d||pad_{21}(I_{Z}^{B^{ast }}(w))||pad_{l}(I_{Z}^{B^{ast }}(y))||pad_{l}(I_{Z}^{B^{ast }}(y^{prime }))||{ ilde {k}}in B^{ast }} .

Для целого l > 0 {displaystyle l>0} , байтовой строки σ ∈ B ∗ {displaystyle sigma in B^{ast }} , для которой L ( σ ) ≥ 2 l + 53 {displaystyle L(sigma )geq 2l+53} ,

C S e c o d e ( l , σ ) = d e f ( [ σ ] 0 64 , I B ∗ Z ( [ σ ] 64 85 ) , I B ∗ Z ( [ σ ] 85 85 + l ) , I B ∗ Z ( [ σ ] 85 + l 85 + 2 l ) , [ σ ] 85 + 2 l L ( σ ) ) ∈ B 64 × Z × Z × Z × B ∗ {displaystyle CSecode(l,sigma ){stackrel {mathrm {def} }{=}}({Bigl [}sigma {Bigr ]}_{0}^{64},I_{B^{ast }}^{Z}({Bigl [}sigma {Bigr ]}_{64}^{85}),I_{B^{ast }}^{Z}({Bigl [}sigma {Bigr ]}_{85}^{85+l}),I_{B^{ast }}^{Z}({Bigl [}sigma {Bigr ]}_{85+l}^{85+2l}),{Bigl [}sigma {Bigr ]}_{85+2l}^{L(sigma )})in B^{64} imes Z imes Z imes Z imes B^{ast }} .

Процесс генерирования подписи

Алгоритм. Генерирование цифровой подписи ACE.
Вход: открытый ключ ( N , h , x , e ′ , k ′ , s ) {displaystyle (N,h,x,e^{prime },k^{prime },s)} и соответствующий закрытый ключ ( p , q , a ) {displaystyle (p,q,a)} и байтовая строка M ∈ B ∗ {displaystyle Min B^{ast }} , 0 ≤ L ( M ) ≤ 2 64 {displaystyle 0leq L(M)leq 2^{64}} .
Выход: байтовая строка — цифровая подпись σ ∈ B ∗ {displaystyle sigma in B^{ast }} .

Замечания

В схемах шифрования и цифровой подписи ACE используются некоторые вспомогательные функции(такие как, например, UOWHash,ESHash и другие), описание которых выходит за рамки данной статьи. Подробнее о данных функциях можно найти в.

Реализация, применение и производительность

Схема шифрования ACE рекомендована проектом NESSIE (New European Schemes for Signatures, Integrity and Encryption) как асимметричная схема шифрования. Пресс-релиз датирован февралем 2003.
Обе схемы были реализованы в ANSI C, с использованием пакета GNU GMP. Тесты были проведены на двух платформах: Power PC 604 model 43P под системой AIX и 266 MHz Pentium под системой Windows NT. Таблицы показателей приведены ниже:
Таблица 1. Временные затраты на базовые операции.

Таблица 2. Производительность схем шифрования и цифровой подписи.