Тестирование скорости выполнения протокола

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

3.3.1 Обнаружение наиболее вычислительно сложной операции. Приведём достаточно абстрактную версию алгоритма аутентификации. Здесь не указаны процедуры принятия и посылки сообщения ключом и автомобилем, так как эти процедуры неизбежно будут присутствовать в конечном устройстве. В алгоритме рассмотрена исключительно часть системы, ответственная за трудоёмкие криптографические операции и математические процедуры, которые необходимо выполнить устройству для успешного осуществления протокола аутентификации:

1 Ключ посылает на автомобиль запрос на авторизацию и ждёт ответа.

2 Автомобиль генерирует случайное число r. После чего вычисляет R=rG и S=rQ. R возвращается на ключ, точка S остаётся в секрете.

3 Ключ, получив R, вычисляет kR = rkG = S` и передаёт S` на автомобиль.

4 Автомобиль проверяет S=S` и производит разблокировку автомобиля.

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

Второй пункт алгоритма требует от автомобиля сгенерировать случайную последовательность r. Время работы генератора случайных чисел линейно зависит от количества необходимых сгенерированных бит. Однако правильно спроектированный генератор заранее накопит необходимое количество энтропии и сгенерирует случайную последовательность очень быстро. В данной работе был спроектирован генератор, который удовлетворяет этому требованию и время его работы не должно оказать значительного влияния на время работы всей процедуры аутентификации пользователя транспортного средства.

Далее во втором пункте системе на стороне автомобиля необходимо произвести операцию скалярного умножения в поле эллиптической кривой. Это достаточно трудоёмкая операция. Целью данного раздела мы ставим исследование времени выполнения этой операции. Во втором пункте алгоритма таких процедур необходимо выполнить две, однако, вторая процедура может быть выполнена уже после отправки ответа на ключ, поэтому мы исключим задержку вносимую вычислением второго скалярного произведения во втором пункте алгоритма.

В третьем пункте алгоритма ключ принимает данные переданные автомобилем и снова производит трудоёмкую операцию скалярного произведения в поле эллиптической кривой. Это наиболее узкое место системы в плане времени работы, так как достаточно трудно вычислимая процедура выполняется на небольшом устройстве с ограниченной вычислительной мощностью. Положительная сторона приведённого алгоритма в отличие от распространённого алгоритма ECDSA в том, что на ключе выполняется только одна операция скалярного умножения. Выходит, что часть процедуры аутентификации выполняет автомобиль, способный обладать менее ограниченным в вычислительном плане процессорным устройством.

В четвёртом пункте после передачи сообщения, подтверждающего аутентичность ключа на автомобиль, автомобилю остаётся сверить переданную переменную с вычисленной. Данная операция достаточно тривиальна и не занимает значительного времени во всей процедуре работы системы.

Таким образом, две наиболее трудоёмкие операции – это операции скалярного умножения в поле эллиптической кривой. Первая из двух операций выполняется на процессоре транспортного средства, который способен обладать достаточно большой вычислительной мощностью, однако всё-таки следует произвести оценку ожидаемого времени работы этой операции. Вторая операция скалярного умножения выполняется на ограниченном в вычислительном плане устройстве, автомобильном ключе. Это наиболее узкое место системы и необходимо в первую очередь обратить внимание на оценку времени работы этой части системы.

3.3.2 Моделирование в среде схемотехнического моделирования. Для выяснения узких в плане времени работы мест системы, необходимо провести моделирование в среде схемотехнического моделирования. Данная мера позволит оценить целесообразность реализации конечного устройства и возможно некоторые дальнейшие необходимые улучшения, которые важно произвести прежде, чем производить дальнейшее проектирование системы. Изображение модели приведено на рисунке 3.1.

В качестве среды моделирования выберем Proteus. Proteus – среда для проектирования и отладки электронных устройств, в том числе выполненных на основе микроконтроллеров различных семейств. Данная среда позволяет произвести симуляцию работы реального микроконтроллера и получить представление о времени работы проектируемых алгоритмов. Для вывода информации из микроконтроллера используется интерфейса USART, а именно подключенный через него виртуальный терминал.

Рисунок 3.1 – Модель устройства в среде моделирования

Время работы операций на микроконтроллере младших семейств не станет ни значительно больше, ни значительно меньше. Например, если рассмотреть микроконтроллер Atmega 8, не смотря на сильное отличие его от микроконтроллера Atmega 256, микроконтроллер сможет реализовать приведённый алгоритм так же эффективно, как и его более продвинутая версия. Так как набор инструкций на обоих микроконтроллерах одинаковый и разрядность системной шины, как на микроконтроллере Atmega 256, так и на микроконтроллере Atmega 8 равны 8 битам. Для проверки времени выполнения наиболее трудоёмкой операции запустим моделирование с кодом, изображённым на рисунке 3.2.

Рисунок 3.2 – Фрагмент кода программы тестирования скорости выполнения алгоритма в среде разработки Sublime

Данная программа производит умножение базовой точки на скаляр 4 раза, после чего производит умножение произвольной точки на скаляр 4 раза. Результаты времени работы в количестве циклов программа выводит на виртуальный терминал по интерфейсу USART. Данная программа позволяет оценить количество циклов 8-битного микроконтроллера, которое необходимо потратить на вычисление операции умножения точки эллиптической кривой на скаляр. Результаты работы программы приведены на рисунке 3.3.

Рисунок 3.3 – Результаты работы программы

Так же у выбранной библиотеки существует версия, оптимизированная по размеру кода программы. Данная версия предназначена для микроконтроллеров с ограниченными ресурсами памяти. Ниже, на рисунке 3.4, приведены результаты выполнения версии программы, основанной на библиотеке, оптимизированной по размеру.

Как видно на рисунке 3.4, версия программы, оптимизированая для работы на микроконтроллерах с малым объёмом памяти программ выполняется почти за такое же количество циклов, как версия программы оптимизированная исключительно на скорость работы. Это позволяет нам использовать более дешёвые микроконтроллеры с меньшим объёмом памяти программ.

Рисунок 3.4 – Результаты работы упрощённой программы

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

Таблица 3.1 – Время выполнения алгоритма

По приведённой таблице можно сделать предсказуемы вывод, что с ростом частоты микроконтроллера прямо пропорционально уменьшается время работы алгоритма. Естественно было бы выбрать наибольшую частоту, которая сводит время работы алгоритма к минимуму, однако при реализации схемы, работающей на частоте свыше 16 Мгц могут возникнуть трудности. В то же время 0, 87–0, 88 секунд – это достаточно небольшое время, которое вряд ли вызовет какой-то дискомфорт у пользователя транспортного средства.

Следовательно, в данной работе мы будем полагать, что полное время работы каждого устройства – это приблизительно одна секунда, а полное время работы алгоритма аутентификации составляет порядка двух секунд. Это не идеальное решение, однако это время позволяет реализовать полноценный алгоритм аутентификации на надёжной основе криптографии эллиптических кривых.

Частота работы микроконтроллера – 16 Мгц. Это позволит быстрее выполнять трудоёмкие операции и вызывать меньше дискомфорта у пользователя транспортного средства.