ACE Encrypt

Материал из testwiki
Перейти к навигации Перейти к поиску

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 — множество целых чисел.
F2[T] — множество одномерных полиномов с коэффициентами в конечном поле F2 с числом элементов поля — 2.
Aremn — такое целое число r{0,...,n1}, для которого Ar(modn) при целом n>0 и AZ.
Aremf — такой полином rF2[T] с deg(r)<deg(f), такой что Ar(modf) при A,fF2[T],f0.

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

A — множество всевозможных строк.
An — множество всевозможных строк длины n.
Для xAL(x) — длина строки x. Обозначения для длины нулевой строки — λA.
Для x,yA x||y — результат конкатенации строк x и y.

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

b=def{0,1}

 — множество битов.
Рассмотрим множества вида

b,bn1,(bn1)n2,...

. Для такого множества A определим нулевой элемент:

0b=def0b;
0An=def(0A,...,0A)An для n>0.


Определим B=defb8 как множество байтов, а W=defb32 как множество слов.

Для

xA

с

A{b,B,W}

и

l>0

определим оператор заполнения:

padl(x)=def{x,L(x)lx||0AlL(x),L(x)<l.

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

Оператор преобразования Isrcdst:srcdst выполняет преобразования между элементами Z,F2[T],b,B,W.

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

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

В схеме шифрования ACE задействованы два типа ключей:
открытый ключ ACE: (P,q,g1,g2,c,d,h1,h2,k1,k2).
закрытый ключ ACE: (w,x,y,z1,z2).
Для заданного параметра размера m, такого что 1024m16384, компоненты ключей определяются следующим образом:
q — 256-битное простое число.
P — m-битное простое число, такое что P1(modq).
g1,g2,c,d,h1,h2 — элементы {1,...,P1} (чей мультипликативный порядок по модулю P делит q).
w,x,y,z1,z2 — элементы {0,...,q1}.
k1,k2 — элементы B, для которых L(k1)=20l+64 и L(k2)=32l/16+40, где l=m/8 и l=Lb((2l/4+4)/16).

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

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

  1. Сгенерировать случайное простое число q, такое что 2255<q<2256.
  2. Сгенерировать случайное простое число P, 2m1<P<2m, такое что P1(modq).
  3. Сгенерировать случайное целое число g1{2,...,P1}, такое что g1q1(modP).
  4. Сгенерировать случайные целые числа w{1,...,q1} и x,y,z1,z2{0,...,q1}
  5. Вычислить следующие целые числа в {1,...,P1}:

    g2g1wremP,


    cg1xremP,


    dg1yremP,


    h1g1z1remP,


    h2g1z2remP.

  6. Сгенерировать случайные байтовые строки k1B20l+64 и k2B2l/16+40, где l=LB(P) и l=LB((2l/4+4)/16).
  7. Вернуть пару открытый/закрытый ключ

    ((P,q,g1,g2,c,d,h1,h2,k1,k2),(w,x,y,z1,z2))

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

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

(s,u1,u2,v,e),


где компоненты определяются следующим образом:
u1,u2,v — целые числа из {1,...,P1} (чей мультипликативный порядок по модулю P делит q).
s — элемент W4.
e — элемент B.
s,u1,u2,v назовём преамбулой, а e — криптограммой. Если текст — строка из l байт, то тогда длина e равна l+16l/1024.

Необходимо ввести функцию

CEncode

, которая представляет шифротекст в виде байтовой строки, а также обратную функцию

CDecode

. Для целого

l>0

, символьной строки

sW4

, целых

0u1,u2,v<256l

, и байтовой строки

eB

,

CEncode(l,s,u1,u2,v,e)=defIWB(s)||padl(IZB(u1))||padl(IZB(u2))||padl(IZB(v))||eB.


Для целого

l>0

, байтовой строки

ψB

, для которой

L(ψ)3l+16

,

CDecode(l,ψ)=def(IBW([ψ]016),IBZ([ψ]1616+l),IBZ([ψ]16+l16+2l),IBZ([ψ]16+2l16+3l),[ψ]16+3lL(ψ))W4×Z×Z×Z×B.

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

Алгоритм. Асимметричный процесс шифрования ACE.
Вход: открытый ключ (P,q,g1,g2,c,d,h1,h2,k1,k2) и байтовая строка MB.
Выход: байтовая строка — шифротекст ψ , полученный из M.

  1. Сгенерировать случайное r{0,...,q1}.
  2. Сгенерировать преамбулу шифротекста:
    1. Сгенерировать sW4.
    2. Вычислить u1g1rremP, u2g2rremP.
    3. Вычислить α UOWHash(k1,LB(P),s,u1,u2)Z; заметим, что 0<α <2160.
    4. Вычислить vcrdα rremP.
  3. Вычислить ключ для операции симметричного шифрования:
    1. h1~h1rremP, h2~h2rremP.
    2. Вычислить kESHash(k,LB(P),s,u1,u2,h1~,h2~)W8.
  4. Вычислить криптограмму eSEnc(k,s,1024,M).
  5. Закодировать шифротекст:

    ψ CEncode(LB(P),s,u1,u2,v,e).

  6. Вернуть ψ .

Перед запуском процесса симметричного шифрования входное сообщение

MB

разбивается на блоки

M1,...,Mt

, где каждый блок кроме, возможно, последнего имеет 1024 байт. Каждый блок шифруется потоковым шифратором. Для каждого зашифрованного блока

Ei

вычисляется 16-байтовый код аутентификации. Получаем криптограмму

e=E1||C1||...||Et||Ct.

L(e)=L(M)+16L(M)/m

. Заметим, что если

L(M)=0

, то

L(e)=0

.

Алгоритм. Симметричный процесс шифрования ACE.
Вход: (k,s,M,m)W8×W4×Z×B m>0
Выход: eBl, l=L(M)+16L(N)/m.

  1. Если M=λB, тогда вернуть λB.
  2. Проинициализировать генератор псевдо-случайных чисел:

genStateInitGen(k,s)GenState

  1. Сгенерировать ключ kAXUAXUHash:

(kAXU,genState)GenWords((5Lb(m/64)+24),genState)..

  1. eλB,i0.
  2. Пока i<L(M), выполнять следующее:
    1. rmin(L(M)i,m).
    2. Сгенерировать значения масок для шифрования и MAC:
      1. (maskm,genState)GenWords(4,genState).
      2. (maske,genState)GenWords(r,genState).
    3. Зашифровать текст: enc[M]ii+rmaske.
    4. Сгенерировать аутентификационный код сообщения:
      1. Если i+r=L(M), тогда lastBlock1; иначе lastBlock0.
      2. macAXUHash(kAXU,lastBlock,enc)W4.
    5. Обновить шифротекст: ee||enc||IWB(macmaskm).
    6. ii+r.
  3. Вернуть e.

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

Алгоритм. Процесс дешифрования ACE.
Вход: открытый ключ (P,q,g1,g2,c,d,h1,h2,k1,k2) и соответствующий закрытый ключ (w,x,y,z1,z2), байтовая строка ψB.
Выход: Расшифрованное сообщение MBReject.

  1. Дешифровать шифротекст:
    1. Если L(ψ)<3LB(P)+16, тогда вернуть Reject.
    2. Вычислить:

      (s,u1,u2,v,e)CDecode(LB(P),ψ)W4×Z×Z×Z×B;


      заметим, что 0u1,u2,v<256l, где l=LB(P).
  2. Подтвердить преамбулу шифротекста:
    1. Если u1P или u2P или vP, тогда вернуть Reject.
    2. Если u1q1remP, тогда вернуть Reject.
    3. reject0.
    4. Если u2u1wremP, тогда reject1.
    5. Вычислить αUOWHash(k1,LB(P),s,u1,u2)Z; заметим, что 0α2160.
    6. Если vu1x+αyremP, тогда reject1.
    7. Если reject=1, тогда вернуть Reject.
  3. Вычислить ключ для процесс симметричного дешифрования:
    1. h1~u1z1remP, h2~u1z2remP.
    2. Вычислить kESHash(k2,LB(P),s,u1,h1~,h2~)W8.
  4. Вычислить MSDec(k,s,1024,e);заметим, что SDec может вернуть Reject.
  5. Вернуть M.

Алгоритм. Операция дешифрования SDec.
Вход: (k,s,m,e)W8×W4×Z×B m>0
Выход: Расшифрованное сообщение MBReject.

  1. Если e=λB, тогда вернуть λB.
  2. Проинициализировать генератор псевдо-случайных чисел:

    genStateInitGen(k,s)GenState

  3. Сгенерировать ключ kAXUAXUHash:

    (kAXU,genState)GenWords((5Lb(m/64)+24),genState)..

  4. MλB,i0.
  5. Пока i<L(e), выполнять следующее:
    1. rmin(L(e)i,m+16)16.
    2. Если r0, тогда вернуть Reject.
    3. Сгенерировать значения масок для шифрования и MAC:
      1. (maskm,genState)GenWords(4,genState).
      2. (maske,genState)GenWords(r,genState).
    4. Подтвердить аутентификационный код сообщения:
      1. Если i+r+16=L(M), тогда lastblock1; иначе lastblock0.
      2. macAXUHash(kAXU,lastBlock,[e]ii+r)W4.
      3. Если [e]ri+ri+r+16IWB(macmaskm), тогда вернуть Reject.
    5. Обновить текст: MM||([e]ii+r)maske).
    6. ii+r+16.
  6. Вернуть M.

В схеме цифровой подписи ACE задействованы два типа ключей:
открытый ключ цифровой подписи ACE: (N,h,x,e,k,s).
закрытый ключ цифровой подписи ACE: (p,q,a).
Для заданного параметра размера m, такого что 1024m16384, компоненты ключей определяются следующим образом:
p — m/2-битное простое число, для которого (p1)/2 — тоже простое.
q — m/2-битное простое число, для которого (q1)/2 — тоже простое.
N — N=pqи может иметь как m, так и m1 бит.
h,x — элементы {1,...,N1} (квадратичные остатки по модулю N).
e — 161-битное простое число.
a — элемент {0,...,(p1)(q1)/41}
k — элементы B184.
s — элементы B32.

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

  1. Сгенерировать случайные простые числа p,q, такие что (p1)/2 и (q1)/2 — тоже простые, и

    2m11<p<2m1, 2m21<q<2m2, и pq,


    где

    m1=m/2 и m1=m/2.

  2. Положить Npq.
  3. Сгенерировать случайное простое числоe, где 2160e2161.
  4. Сгенерировать случайное h{1,...,N1}, при условии gcd(h,N)=1 и gcd(h±1,N)=1, и вычислить h(h)2remN.
  5. Сгенерировать случайное a{0,...,(p1)(q1)/41} и вычислить xharemN.
  6. Сгенерировать случайные байтовые строки kB184, и sB32.
  7. Вернуть пару открытый ключ/закрытый ключ

    ((N,h,x,e,k,s),(p,q,a)).

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

Подпись в схеме цифровой подписи ACE имеет вид (d,w,y,y,k~), где компоненты определяются следующим образом:
d — элемент B64.
w — целое число, такое что 2160w2161.
y,y — элементы {1,...,N1}.
k~ — элемент B;заметим, что L(k~)=64+20LB((L(M)+8)/64), где M — подписываемое сообщение.

Необходимо ввести функцию

SEncode

, которая представляет подпись в виде байтовой строки, а также обратную функцию

SDecode

. Для целого

l>0

, байтовой строки

dB64

, целых

0w25621

и

0y,y<256l

, и байтовой строки

k~B

,

SEncode(l,d,w,y,y,k~)=defd||pad21(IZB(w))||padl(IZB(y))||padl(IZB(y))||k~B.


Для целого

l>0

, байтовой строки

σB

, для которой

L(σ)2l+53

,

CSecode(l,σ)=def([σ]064,IBZ([σ]6485),IBZ([σ]8585+l),IBZ([σ]85+l85+2l),[σ]85+2lL(σ))B64×Z×Z×Z×B.

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

Алгоритм. Генерирование цифровой подписи ACE.
Вход: открытый ключ (N,h,x,e,k,s) и соответствующий закрытый ключ (p,q,a) и байтовая строка MB, 0L(M)264.
Выход: байтовая строка — цифровая подпись σB.

  1. Произвести следующие действия для хеширования входных данных:
    1. Сгенерировать случайно ключ хеша k~B20m+64, такой что m=Lb((L(M)+8)/64).
    2. Вычислить mhIWZ(UOWHash(k~,M)).
  2. Выбрать случайное y~{1,...,N1}, и вычислить yy~2remN.
  3. Вычислить x(y)rhmhremN.
  4. Сгенерировать случайное простое число e, 2160e2161, и его подтверждение корректности (w,d): (e,w,d)GenCertPrime(s). Повторять этот шаг до тех пор, когда ee.
  5. Положить rUOWHash(k,LB(N),x,k~)Z; заметим, что 0r<2160.
  6. Вычислить yhbremN, где

    be1(ar)rem(pq),


    и где p=(p1)/2 и q=(q1)/2.
  7. Закодировать подпись:

    σSEncode(LB(N),d,w,y,y,k~).

Замечания

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

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

Схема шифрования 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. Временные затраты на базовые операции.

Power PC Pentium
Размер операнда(байт) Размер операнда(байт)
512 1024 512 1024
Умножение 3.5 * 10^(-5) сек 1.0 * 10^(-4) сек 4.5 * 10^(-5) сек 1.4 * 10^(-4) сек
Возведение в квадрат 3.3 * 10^(-5) сек 1.0 * 10^(-4) сек 4.4 * 10^(-5) сек 1.4 * 10^(-4) сек
Потенцирование 1.9 * 10^(-2) сек 1.2 * 10^(-1) сек 2.6 * 10^(-2) сек 1.7 * 10^(-1) сек


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

Power PC Pentium
Постоянные затраты (мсек) МБит/сек Постоянные затраты (мсек) МБит/сек
Шифрование 160 18 230 16
Дешифрование 68 18 97 14
Подпись 48 64 62 52
Подпись (начальная установка) 29 41
Верификация 52 65 73 53

Литература

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

Ссылки