У меня уже не первый год висит нерешенным вопрос следующего вида: необходимо сравнить вычислительную трудоемкость двух алгоритмов - ну, например, блочного шифрования, хеширования... И если для универсальных процессоров величина cycles per byte - цисло тактов процессора для обработки одного байта исходной информации фактически стала стандартом де-факто в кругу разработчиков подобных схем, то вот с FPGA и ASIC разброд и шатания.

Я прекрасно понимаю разработчиков Xilinx и Altera (да и остальных наверное), которые в определенный момент перестали вычислять Gate Equivalent для дизайна. Более того, собственные изыскания на эту тему показали громадный разброс GE в зависимости от того, как именно записать алгоритм в VHDL, расставить промежуточные триггера, использовать ли DSP и т.д. И до сего момента мне, в общем-то, вполне хватало сравнений именно реализаций схем в старой доброй ISE9, в которой GE еще считаются, при некоторых равных предположениях для алгоритмов - либо полностью параллельная схема, либо каждый такт только одну итерацию считаем, все константы реализуем логикой или храним в BRAM, и т.д.

Но вот возникла задачка: на конференции CHES 2010 Axel Poschmann, San Ling, and Huaxiong Wang взяли да засунули наш ГОСТ 28147-89 в 650GE с помощью Synopsys DesignCompiler для библиотеки UMC L180 0.18μm, а в 2011 году китайские негодяи предложили ряд атак на него, пользуясь регулярностью ключевой развертки (http://eprint.iacr.org/2011/558). Ну и возникает вопрос, а если эту самую ключевую развертку неким образом модифицировать, насколько "потяжелеет" реализация? Здесь уже синтез FPGA не годится...

Вы уж извините, что столь нудно и подробно, но просто проблемка специфическая - моей задачей не ставится разработка реального чипа, а получение "сферической лошади в вакууме", но сравнимой с уже посчитанной для ASIC. Вот и возник вопрос: а есть что-нибудь достаточно доступное (особенно с торрентов, ибо мне нужна только итоговая циферка, хоть транзисторов, хоть GE - начальство явно Synopsys не оплатит, а в торрентах, его, увы, очень мало, даже китайских), в чем бы это можно было посчитать?

Вроде простая задача, тем более что в эти 650GE не входят триггеры для хранения ключа (и понятно, почему ), а вот найти что-то доступное для не сильно продвинутого в ASIC не удалось даже в китайском гугле...

Synopsys DesignCompiler сообщает площадь проекта для той библиотеки, для которой этот проект скомпилен.
из документации к библиотеке берется площадь элемента NAND2 с 0-вым выходом
поделив первое на второе получается оценка в GE

--------------------

проще найти компилер и библиотеку, чем, например, дать свой код для оценки китайцам

но общие зависимости (то есть пропорция) между затратами в ISE и в DC они сохраняются - то есть получите коэффициент пересчета LUT-ов в GE из старого проекта и помножте LUT-ы в новом - вполне коректная для такого разговора оценка получицца

---------------------

ну и еще - результат работы DC (площадь, GE) зависит от многих параметров - какие опции (например DW или compile_ultra), какие констрейны, как оптимизировано (например BRAM для ксайлинса обычно улучшает по сравнению с логикой, а для DC ухудшает) и т.д. да в конце концов, насколько криво написан RTL

================

и мне покоя не дает цифра 650 (очень мало) - это получается что-то проще DES-а? (я в криптографии профан-любитель, пару лекций послушал когда-то давно, про ГОСТы вообще не знаю)

Это я понимаю, но с


не согласен - живых ссылок найти не удалось
Если знаете - плиз, отпишите в личку...


Если дизайн где-нибудь на 300000GE, то да. А когда речь идет о сотнях, тут уже сильно сказывается природа LUT-ов. Ведь по сути, это 32 или 64 бита памяти, которые по 5 или 6 входам (это я применительно к Virtex5) выдают однобитовый результат. А в асике вполне возможно трех или 5-битовые подстановки (хотя ее Xilinx через мультиплексор делает - красота!) эффективно нарисовать. Поэтому сравнить свои поделки с вышеприведенной работой с точностью не плюс/минус километр - увы.


Ну для себя на FPGA обычно делаю оптимизацию по площади, финальные "забеги" - с повышенной точностью (хотя тогда дизайн разводится почти сутки до Static Timing Report), а про BRAM уже говорил - или все алгоритмы используют его, или все на LUT-ах. В качестве констрейнов мне наш гуру, пока не уволился, пропагандировал правило - объем заполнения кристалла не выше 70% (дальше синтезатор тупит), частота - 50% от максимально возможной кристалла. По его работам (в-основном, fully pipelined - не знаю русского термина? криптографические схемы, сколько копий удастся затолкать в дизайн, а дальше некая логика анализа результатов перебора), если в них не укладываться, обычно проще было поставить два кристалла рядом, и разбить алгоритм пополам. Хотя перед пенсией ГОСТ он любовно "вылизал" до 450МГц на Virtex5, если не ошибаюсь... Уперся в тепловыделение конкретных закупленных плат.


Ну они там "жульничают" вовсю, на самом деле... Так, если посмотрите, то 256 бит ключа берутся "из воздуха" (а я их обычно "защелкиваю" в триггеры), есть еще натяжки с точки зрения "жизненной" а не теоретической реализации. Так, хотя стандарт ничего не говорит о том, что подстановки (8 4-битных) должны быть разные, понятно, что применение одной подстановки к 4-битным блокам по очереди тоже позволяет оптимизировать дизайн, ну и т.д.

А я по сути в схемотехнике профан-любитель, но иногда математики-теоретики очень хотят знать, как выглядят те или иные конструкции "в железе". Приходится вспоминать институтские крохи

можно скачать для актела (actel.com) бесплатные тулзы и посмотреть на результаты - там плис без лутов и оценка в гейтах будет очень близка к АЗИКу

также можно припомнить как измерять диаметр тонкой проволочки - нужно намотать несколько витков и разделить измеренную толщину на кол-во витков для гейтов этот метод тоже работает

можно получить доступ в специальные разделы форума и там узнать про DC и библиотеки

-----------

мое мнение, что для такой приблизительно-теоретической оценки любой метод имеет достаточную точность (скажем так: DC и не та библиотека может быть менее точным, чем ISE)

Ну я тут немножко поковырялся в ПЛИСах для реализации столь скудных по GE алгоритмов... Рассмотрел узел ключевой развертки. Начал с 2800GE, закончил 722... А если ключ фиксированный (что, кстати, нонсенс - компрометация его приводит к отказу всей системы безопасности, зависящей от ключа) вообще 160 с небольшим... Но тут 5-6 входовость LUT-ов служит ограничением по GE - минимизировать не удается.

А можно на ПЛИСах как-то синтезировать выборку 32 или 4 битного блока из 256-битного входного сигнала без мультиплексоров? А на АСИКах? А то подозреваю, что автор работы, что рассмотрена выше, имеет ввиду что-то другое... Но не говорит.

А на ваш фтп меня пока не пущають

Вопрос поставлен комплексно конечно....
1) Определить вычислительную трудоемкость алгоритмов, т.е. число тактов процессора для обработки одного байта....

Для определения "число тактов процессора для обработки одного байта" если алгоритм только в виде идеи и блок-схемы существует предложить ничего конкретного не могу... тут математическое моделирование помочь скорее может.
Если алгоритм реализован на уровне RTL - запустите симуляцию и узнаете точно сколько тактов ему нужно.

2) "Китайци реализовали ГОСТ 28147-89 в 650GE с помощью Synopsys DesignCompiler для библиотеки UMC L180 0.18μm...."
Понятно
"А если эту самую ключевую развертку неким образом модифицировать, насколько "потяжелеет" реализация"?

Что значит потяжелеет? В мире ASIC это означает площадь кристала.
Вам надо сделать оценку площади будущего кристала или всётаки сравнить 2 RTL реализации?

а) Если сравнить реализации, то получите из ISE репорт про количество тригеров и гейтов и сравнивайте что больше, а что меньше и на сколько %
б) Если надо сделать оценку площади будущего кристала, то тут хуже...
- Достаточно точно можно получить эту оценку отсинтезив проект в Synopsys DesignCompiler в вашей UMC L180 0.18μm.
Площадь всех тригеров и гейтов будет занимать примерно 70% будущего кристала.
- Менее точно можно прикинуть так: Вычисляем сколько гейтов на тригер получилось в предыдущем RTL . Из нового RTL узнаём сколько у вас тригеров. Узнаём сколько получится гейтов (зная сколько гейт\тригер). Находим насколько % больше гейтов и тригеров в новом дизайне. увеличиваем на этот процент площадь....

Как-то так.

Да, а китайци DFT вставили? А-то это есчё площади процентов 50 добавит при ваших 650 GE (тригеров 100 я так полагаю). А-то сюрпризом будет если ASIC сделать....

Во-первых, в этом абзаце речь шла об универсальных процессорах, то-есть система команд дана нам свыше, и ничего менять нельзя. Но эта характеристика тоже важна, поверьте.
Во-вторых, рад бы, но реализация, сами понимаете, авторская, закрытая, исходников нет.


Сравнить. Но при том, что сделать реализацию в синопсисе я не могу за отсутствием синопсиса. Реализации на ПЛИСах, хоть и показывают некую среднюю температуру по больнице, но иногда очень сильно лажают. На СБИСах, похоже, можно сделать гораздо лучше.
Вариант модификации ГОСТа, например, подразумевает наличие двух различных подстановок - по 4 включения каждой на итерацию. Отсюда, видится, нужно добавление одной подстановки плюс демультиплексор, зависящий от конкретного шага алгоритма. Если эта функция тривиальна - 4 верхних подстановки равны, 4 нижних подстановки равны - ну тут все просто элементарно. Но вот по криптоанализу это не всегда есть хорошо ((


Как сравнить 30 LUT-ов и 53 FF-ов c 853 GE? что больше?

Повторюсь, нет у меня синопсиса. Был бы (тут молитва к модераторам - пустите на ftp, если у вас валяется!) - сгенерил бы. Пока у меня на ПЛИСах есть ключевая развертка примерно в 700 GE если ключ извне и 160 GE если ключ фиксирован... Площадь не нужна - обычно все меряются именно чистыми GE... Но это и рядом не лежит с 650 GE на всю схему. Т.е. я не могу утверждать, что моя vhdl интерпретация госта идеальна. Можно ведь и на 30 килогейтов написать...

Ну и наверное вопрос по ходу: вот у нас висит внешний (для алгоритма) ключ 256 бит. Из него, в зависимости от такта работы алгоритма шифрования, надо выбрать 32-битное слово, а потом, опять же в зависимости от такта, из этого 32-битного слова надо выбрать 4-битное слово, которое, сложив с 4 битами промежуточных результатов Х (и с carry - мы же по модулю 2^32 работаем!) занести в память по адресу, где лежало Х... Так вот, выборка ключевой информации на ПЛИСах как-нибудь кроме мультиплексоров решается? Если ключ фиксированный, САПР генерит ROM нужных размеров, и там это все очень экономично получается. А в случае, когда ключ - это переменная?


Я привел ссылку на их работу выше. Более достоверной информации у меня нет. И что это за DFT? Понятно, что не Direct Fourier Transform, но вот дальше гугль заманчиво обширен ))

Немного не так. DFT это Design for Testability, встраиваемая логика для автоматической проверки работоспособности схемы при ее изготовлении на фабрике. Увеличивает размер триггеров процентов на 10, и добавляет логику самого DFT (в виде комбинаторики и триггеров ), а также дополнительные соединения. Таким образом, добавление DFT увеличивеат общую площадь и количество селлов, а еще уменьшает Fmax схемы.

Какой там тестинг?! Китайцы вырезали все, что могли, в том числе положили ключ шифрования как константу на этапе синтеза, что существенно облегчило схему.

с синопсисом я помочь не могу, но еще одну странность отмечу:

650 это очень мало, чип из такого не делается

если у этого чипа будут какие-то ножки наружу - то одна ножка будет больше 650 гейтов по площади

а если это все-таки какой-то фрагмент, который 100000 раз повторяется в проекте, то возможно накладные расходы (доставка значений ключа и сообщения до этого блока) может быть гораздо больше чем логика в блоке

так же есть оптимизация по скорости, а не по площади - может быть на 650 гейт будет работать на 10МГц, а чтоб заработал на 100МГц понадобится 2000 гейт
также для скорости могут вставлятся дублирующие триггеры и логика

также между ячейками оставляются пространства для проводов и т.д.

А что не понятно?
засовываем RTL1 в ISE и читаем репорт - 53 FF
засовываем RTL2 в ISE и читаем репорт - 60 FF
Разве не очевидно что больше и на сколько процентов?

Ваша постановка задачи абсолютно не ясна.
Толи вам про эфективность алгоритмов надо поспорить, то-ли про оптимальность реализации разных RTL в FPGA надо поспорить, толи вам вычислить площадь ASIC надо для разных RTL....
Неясно есть ли у вас 2 разных RTL о которых речь, или есть один RTL но у китайцев и вы хотите сравнить с ним алгоритм который есчё в уме, или вы только на уровне идей как-бы реализовать алгоритмы разными способами есчё думаете....
Вы FPGA собираетесь делать или ASIC или формулу изобрести?
Вы определитесь сначала - чё надо и чё у вас есть...

Естественно, не рассматриваются "ножки наружу". То есть, это - по сути аналог IP-Core Xilinx, делаем некое криптоядро для использования снаружи, вокруг вешаются всякие модули приема/передачи информации, соответствия неким протоколам, и т.д., т.е. о входах/выходах алгоритма авторы заботиться и не должны.

Скорость там тоже на уровне - Вы посмотрите внимательно, там за такт работы схемы реально считаются только 4 бита результата 1 итерации ГОСТа (итого, 8 тактов на итерацию, 256 тактов на зашифрование 64 бит открытого текста, и похоже, еще 8 тактов на обмен состояниями). Мне ISE дает оценку 340 МГц из 500 возможных для Virtex5.


Вот не очевидно: как сравнить число LUT и FF ПЛИС c GE ASIC?
На практике для ПЛИС получается так:
1. 100 LUT + 200 FF
2. 200 LUT + 100 FF
и что из них лучше если тупо VHDL скомпилировать под ASIC?
У ПЛИСов фиксировано количество входов LUTов, поэтому для них методы оптимизации совсем другие.


Есть - САПР для ПЛИС. Есть - некоторая сторонняя оценка для СБИС китайцами. Надо: сделать свою оценку для СБИС для (возможной, если придется) модификации алгоритма. Софта для СБИС, увы, нет. Поэтому либо пытаться так модифицировать алгоритм, чтобы обойтись сторонними оценками, либо сделать что-то свое. Но синопсиса, ПОВТОРЮСЬ, в свободном доступе нету. Я много чего искал и находил, но это, похоже, слишком узко, чтоб его ломали варез-группы. Число денег, сколько стоит официальный синопсис, не окупит смысла проводимой работы.
Что надо: показать, что некоторая модификация ключевой развертки ГОСТа не ухудшит его характеристик по скорости: ну, пусть на 10% медленнее станет, или на 10% больше площади кристалла, но не в разы.

И да, речь идет об эффективности алгоритмов. Есть ряд мировых стандартов, в них есть набор рекомендуемых алгоритмов шифрования. Чтобы в них включиться, нужно, помимо требований по стойкости, отвечать требованиям по скорости их реализаций. И тут буквально на каждый такт или GE бороться приходится....

1) никак не сравнить ужа и ежа.
2) сравните тупо количество FF в RTL1 & RTL2 в ISE репортах. Насколько их процентов больше - на столько и площадь станет больше.