Про то, как придумывать хорошие, стойкие к подбору пароли, написано немало статей, в том числе и на Хабре. Сегодня я хочу рассказать про устройство, которое также предназначено для решения этой задачи. На его разработку у меня ушло всего пара дней, а изготовить по готовой документации его можно за несколько часов. Это устройство будет интересно смотреться на вашем столе, а также послужит оригинальным подарком компьютерному гику, сисадмину или специалисту по информационной безопасности.
Итак, знакомьтесь: RANDOMOUSE — генератор случайных символов, встроенный в обычную компьютерную мышку.
Для генерации случайных чисел алгоритмическим способом нужна функция, которая будет при каждом вызове выдавать очередное значение. При этом очень желательно, чтобы эти значения «выглядели» случайными (в разброс), а период повторения последовательности был максимальным (в идеале 2^N-1, где N – разрядность результата).
Функция генерации псевдослучайного числа представляет собой полином вида
задаваемый коэффициентами gi ={0,1} (i = 0,...k).
Для вычисления значения функции может использоваться схема Галуа, как наиболее простая при алгоритмической реализации. Полином задается своими коэффициентами в виде двоичного числа, значение функции f(x) вычисляется по алгоритму.
1. Если младший_бит(x) = 1, то
2. f(x) = (x / 2) xor Полином
3. иначе
4. f(x) = x / 2
5. всё
На следующем шаге вычисленное значение используют в качестве аргумента функции и все повторяется. В качестве выхода генератора используется младший бит значения вычисленного значения.
Существуют полиномы, называемые примитивными, которые дают неповторяющуюся последовательность значений функции максимально возможной длины. Более глубокую теорию по этому вопросу можно почитать, например, здесь.
Понятно, что любой алгоритм при одинаковых входных данных дает одинаковый результат. Поэтому на основе чисто алгоритмических действий можно построить только генератор псевдослучайных чисел — когда последовательность чисел на выходе в конце концов повторится строго в том же порядке. При этом сама последовательность может быть очень длинной, но основная проблема в том, что при инициализации генератора одним и тем же входным значением мы получим всегда одинаковую последовательность чисел на выходе.
Чтобы получить по-настоящему случайную последовательность, помимо алгоритмического генератора нужно использовать физический. В компьютере постоянно происходит множество событий, которые можно считать случайными по отношению к работающей программе. Это обмен данными с памятью и накопителями, ввод данных с клавиатуры и мыши, получение пакетов из сети. В UNIX-подобных ОС есть встроенный датчик случайных чисел /dev/random, который выдает случайные данные, накопленные на основе такого «физического шума». Эти данные можно использовать для генерации начального элемента последовательности случайных чисел или постоянно подмешивать их в результат работы ГСЧ, чтобы получить истинно случайную последовательность.
В рассматриваемом генераторе паролей используются оба механизма генерации случайных чисел: алгоритмический, на основе примитивного полинома, и физический. В качестве аппаратного датчика случайных чисел используется одна из сигнальных линий шины USB. Во время обмена данными между мышкой и компьютером на этой линии «случайным» образом сигнал переключается между значениями 0 и 1, что используется для подмешивания «физического шума» к результатам алгоритмического ГСЧ.
Генератор собран на 8-битном микроконтроллере фирмы Atmel семейства AVR. Благодаря применению микроконтроллера схема получилась очень простой, помимо МК также нужен собственно индикатор и несколько токоограничительных резисторов — по одному на каждый используемый разряд индикатора.
Мною были разработаны две версии генератора — для обычного 7-сегментного индикатора и для «продвинутого» 16-сегментного. Последний вы могли видеть на современной бытовой технике, которая умеет общаться с пользователем на «человеческом языке». Этот вид индикаторов позволяет отобразить любую из букв латинского или кириллического алфавита. К сожалению, 16-сегментного индикатора у меня под рукой не оказалось, поэтому «в металле» я воплотил только 7-сегментный вариант, но схемы и прошивки выкладываю для обоих версий. В случае 7-сегментного индикатора генератор умеет отображать цифры и некоторые буквы.
Принципиальная схема обоих версий (щелкните, чтобы увеличить)
Схемы, исходный код (на ассемблере) и скомпилированные прошивки для обоих версий можно скачать в виде zip-архива (44к).
Номиналы резисторов подбираются исходя из минимального тока, который обеспечивает приемлемую светимость сегментов индикатора. Не стоит сильно перегружать USB-порт, хотя он может выдавать максимум 500мА, обычно он запрограммирован на 100мА, а для повышения лимита подключенное устройство должно указывать это в своем дескрипторе.
Конструкция устройства в основном определяется наличием и формой свободного места внутри мыши. Не забывайте о размещении индикатора так, чтобы его было видно. Лучше, чтобы индикатор просвечивал через полупрозрачную стенку корпуса, тогда вам не придется прорезать под него отверстие и готовое изделие будет смотреться лучше и «фирменнее».
Я разместил МК и резисторы на небольшой плате из стеклотекстолита, изготовленной лазерно-утюжным способом. Индикатор припаивается за один ряд ножек, к ножкам второго ряда плата подключается проводами.
Внутри мыши индикатор с платой были зажаты между двумя ребрами жесткости боковины корпуса (так удачно совпали размеры, даже клей не понадобился).
Три провода (питание, данные и общий) припаиваются к контактам разъема USB-кабеля. Проще всего определить назначение проводов с помощью тестера, воспользовавшись распиновкой USB-разъема (см. схему).
Для программирования МК прямо к его выводам были припаяны тонкие проводники (от витой пары), к которым подключался программатор. После проверки работоспособности схемы проводники отпаиваются. Я пользуюсь USB-программатором USBASP (http://www.fischl.de/usbasp/) и программой AVRDUDE (http://www.nongnu.org/avrdude/). Для однократного программирования (т.е. вы хотите сделать только это устройство, а не заниматься программированием МК в будущем) можно на скорую руку собрать что-то их схем, например, здесь (http://www.123avr.com/07.htm) или поискать «Программатор AVR» и почитать отзывы про конкретную схему. Главное, старайтесь, чтобы провода между последним активным элементом программатора (буферной микросхемой, чипсетом ПК :) и т.п.) и МК были как можно короче.
Если вы захотите модернизировать устройство, вам будет интересно узнать, как оно работает изнутри.
Интерфейс USB использует 4 провода, обозначаемые VCC (питание, +5Вольт), Data- (D-), Data+ (D+), GND (общий провод). Для передачи данных используются линии D+/D-, образующие так называемую «дифференциальную пару». По стандарту, при передаче на одном проводе пары напряжение должно быть не меньше 2,7Вольт, а на другом не больше 0,3Вольт. При приеме уровнем логического нуля считается состояние, в котором напряжение на линии D- не менее чем на 0,2Вольт выше напряжения на линии D+, а уровнем логической единицы — наоборот. Благодаря тому, что в кабеле эти два провода свиты в витую пару, такой протокол обеспечивает высокую помехозащищенность при передаче данных.
Один из проводов из пары подключается ко входу встроенного в МК аналогового компаратора. Это устройство непрерывно сравнивает напряжения на двух своих входах и выдает цифровой сигнал 0 или 1 в зависимости от того, напряжение на каком входе больше. Теоретически, можно было бы подключить к компаратору оба провода пары, но для целей генерации случайного сигнала достаточно одного провода. Ко второму входу подключается внутренний источник опорного напряжения (примерно 1,1Вольт).
Алгоритм работы программы следующий:
1. При включении питания происходит инициализация внутренних устройств МК и портов ввода-вывода (строки 90-134). Порт, используемый для входа компаратора должен всегда быть настроен на ввод без подключения подтягивающего резистора. В противном случае работа USB-интерфейса будет нарушена. После инициализации МК переходит в режим сна, чтобы не тратить зря энергию.
2. Прерывание таймера вызывается с частотой, равной числу возможных значений случайного числа. Благодаря этому периодичность смены значений на индикаторе остается равной 1 секунде независимо от числа значений.
Сразу после включения питания устройство работает в демо-режиме, по очереди отображая все возможные значения по 0,5 секунде каждое (строки 150-171).
Затем происходит переключение в режим начальной инициализации ГСЧ: набор начального значения алгоритмического ГСЧ от физического датчика (строки 173-185).
После инициализации ГСЧ каждое следующее срабатывание таймера приводит к вычислению очередного значения функции ГСЧ и прибавлению младшего бита к случайному значению (строки 187-211). Каждые N циклов (где N равно числу возможных случайных значений) происходит отображение символа, соответствующего случайному значению (подпрограмма DISPLAY_SIGN в подключаемом файле, зависит от числа сегментов), затем текущее случайное значение сбрасывается и цикл начинается сначала.
3. Прерывание аналогового компаратора вызывается каждый раз, когда изменяется его выходное значение (с 0 на 1 или наоборот). Для генерации физического случайного числа используется текущее значение таймера 0, непрерывно считающего с частотой МК (4МГц). Во время начальной инициализации ГСЧ младший бит значения счетчика таймера 0 записывается в младший бит переменной ГСЧ, сдвигая остальные биты в сторону старшего (строки 234-244).
После того, как 32 бита будут набраны, устройство переходит в рабочий режим. В нем значение младших 5 бит счетчика таймера 0 складывается со случайным значением, после чего случайное значение берется по модулю числа возможных значений (строки 247-259).
Для удобства переключения между версиями весь код, данные и константы, зависящие от разрядности индикатора, вынесены в отдельный файл, который включается в основной код. Вы можете создать свой собственный вариант на основе имеющегося.
Соответствие выходов МК и сегментов индикатора обычно выбирают исходя из удобства разводки проводников на плате. В случае, если вы измените схему подключения, вам также придется изменить соответствующую таблицу знакогенератора во включаемом файле. Если используется индикатор с общим анодом (подключенным к +5Вольт), то для зажигания сегмента на выходе МК должен быть 0, если с общим катодом (подключенным к общему проводу), то 1.
Обратите внимание, что в 16-битном варианте реально используются 14 выводов МК, верхняя и нижняя пары сегментов объединены (но каждый подключен через свой резистор). Это может накладывать ограничения на возможности отображения символов. Если вам понадобится разделить эти сегменты, используйте выводы PA0, PA1 (в режиме внутреннего генератора они не используются), изменив подпрограмму DISPLAY_SIGN.
Хотя новые пароли приходится создавать не так уж и часто, описанное устройство может найти другие применения, связанных с генерацией случайных чисел, например вместо кубика в настольных играх. Для удобства работы в различных режимах можно выбрать мышку с дополнительными кнопками и одну из них подключить к МК, доработав прошивку так, чтобы по нажатию этой кнопки переключались таблицы случайных символов или выдавалось следующее случайное число.
Также предложенная схема с минимальными изменениями может быть использована в других устройствах. Первое, что приходит в голову под Новый Год — сделать новогоднюю гирлянду. Для этого вместо индикатора к выходам МК подключаются светодиоды (обычно напряжения 5Вольт хватает на два светодиода, соединенных последовательно, токоограничительные резисторы можно не ставить, если ток через цепочку не будет превышать 20мА), а вместо символов в таблицу знакогенератора записываются комбинации зажигания этих светодиодов. Для подключения цепочек светодиодов большей длины понадобится увеличить напряжение питания (тогда МК нужно будет питать от стабилизатора на 5Вольт) и использовать транзисторные ключи или специализированную микросхему-буфер.
Отдельный вопрос — что делать с физическим датчиком (входом аналогового компаратора). Его можно подключить к проводу достаточной длины (сантиметров 30 должно хватить), сопротивление входа МК весьма высокое и напряжение на входе будет меняться из-за электромагнитных наводок, создавая необходимые случайные импульсы. Если устройство будет питаться от USB (настольный сувенир «мини-елочка»), то вход можно опять же подключить к любой линии данных USB-шины.
Итак, знакомьтесь: RANDOMOUSE — генератор случайных символов, встроенный в обычную компьютерную мышку.
Вначале немного теории
Для генерации случайных чисел алгоритмическим способом нужна функция, которая будет при каждом вызове выдавать очередное значение. При этом очень желательно, чтобы эти значения «выглядели» случайными (в разброс), а период повторения последовательности был максимальным (в идеале 2^N-1, где N – разрядность результата).
Функция генерации псевдослучайного числа представляет собой полином вида
задаваемый коэффициентами gi ={0,1} (i = 0,...k).
Для вычисления значения функции может использоваться схема Галуа, как наиболее простая при алгоритмической реализации. Полином задается своими коэффициентами в виде двоичного числа, значение функции f(x) вычисляется по алгоритму.
1. Если младший_бит(x) = 1, то
2. f(x) = (x / 2) xor Полином
3. иначе
4. f(x) = x / 2
5. всё
На следующем шаге вычисленное значение используют в качестве аргумента функции и все повторяется. В качестве выхода генератора используется младший бит значения вычисленного значения.
Существуют полиномы, называемые примитивными, которые дают неповторяющуюся последовательность значений функции максимально возможной длины. Более глубокую теорию по этому вопросу можно почитать, например, здесь.
Понятно, что любой алгоритм при одинаковых входных данных дает одинаковый результат. Поэтому на основе чисто алгоритмических действий можно построить только генератор псевдослучайных чисел — когда последовательность чисел на выходе в конце концов повторится строго в том же порядке. При этом сама последовательность может быть очень длинной, но основная проблема в том, что при инициализации генератора одним и тем же входным значением мы получим всегда одинаковую последовательность чисел на выходе.
Чтобы получить по-настоящему случайную последовательность, помимо алгоритмического генератора нужно использовать физический. В компьютере постоянно происходит множество событий, которые можно считать случайными по отношению к работающей программе. Это обмен данными с памятью и накопителями, ввод данных с клавиатуры и мыши, получение пакетов из сети. В UNIX-подобных ОС есть встроенный датчик случайных чисел /dev/random, который выдает случайные данные, накопленные на основе такого «физического шума». Эти данные можно использовать для генерации начального элемента последовательности случайных чисел или постоянно подмешивать их в результат работы ГСЧ, чтобы получить истинно случайную последовательность.
Устройство генератора
В рассматриваемом генераторе паролей используются оба механизма генерации случайных чисел: алгоритмический, на основе примитивного полинома, и физический. В качестве аппаратного датчика случайных чисел используется одна из сигнальных линий шины USB. Во время обмена данными между мышкой и компьютером на этой линии «случайным» образом сигнал переключается между значениями 0 и 1, что используется для подмешивания «физического шума» к результатам алгоритмического ГСЧ.
Генератор собран на 8-битном микроконтроллере фирмы Atmel семейства AVR. Благодаря применению микроконтроллера схема получилась очень простой, помимо МК также нужен собственно индикатор и несколько токоограничительных резисторов — по одному на каждый используемый разряд индикатора.
Мною были разработаны две версии генератора — для обычного 7-сегментного индикатора и для «продвинутого» 16-сегментного. Последний вы могли видеть на современной бытовой технике, которая умеет общаться с пользователем на «человеческом языке». Этот вид индикаторов позволяет отобразить любую из букв латинского или кириллического алфавита. К сожалению, 16-сегментного индикатора у меня под рукой не оказалось, поэтому «в металле» я воплотил только 7-сегментный вариант, но схемы и прошивки выкладываю для обоих версий. В случае 7-сегментного индикатора генератор умеет отображать цифры и некоторые буквы.
Принципиальная схема обоих версий (щелкните, чтобы увеличить)
Схемы, исходный код (на ассемблере) и скомпилированные прошивки для обоих версий можно скачать в виде zip-архива (44к).
Номиналы резисторов подбираются исходя из минимального тока, который обеспечивает приемлемую светимость сегментов индикатора. Не стоит сильно перегружать USB-порт, хотя он может выдавать максимум 500мА, обычно он запрограммирован на 100мА, а для повышения лимита подключенное устройство должно указывать это в своем дескрипторе.
Конструкция устройства в основном определяется наличием и формой свободного места внутри мыши. Не забывайте о размещении индикатора так, чтобы его было видно. Лучше, чтобы индикатор просвечивал через полупрозрачную стенку корпуса, тогда вам не придется прорезать под него отверстие и готовое изделие будет смотреться лучше и «фирменнее».
Я разместил МК и резисторы на небольшой плате из стеклотекстолита, изготовленной лазерно-утюжным способом. Индикатор припаивается за один ряд ножек, к ножкам второго ряда плата подключается проводами.
Внутри мыши индикатор с платой были зажаты между двумя ребрами жесткости боковины корпуса (так удачно совпали размеры, даже клей не понадобился).
Три провода (питание, данные и общий) припаиваются к контактам разъема USB-кабеля. Проще всего определить назначение проводов с помощью тестера, воспользовавшись распиновкой USB-разъема (см. схему).
Для программирования МК прямо к его выводам были припаяны тонкие проводники (от витой пары), к которым подключался программатор. После проверки работоспособности схемы проводники отпаиваются. Я пользуюсь USB-программатором USBASP (http://www.fischl.de/usbasp/) и программой AVRDUDE (http://www.nongnu.org/avrdude/). Для однократного программирования (т.е. вы хотите сделать только это устройство, а не заниматься программированием МК в будущем) можно на скорую руку собрать что-то их схем, например, здесь (http://www.123avr.com/07.htm) или поискать «Программатор AVR» и почитать отзывы про конкретную схему. Главное, старайтесь, чтобы провода между последним активным элементом программатора (буферной микросхемой, чипсетом ПК :) и т.п.) и МК были как можно короче.
Подробнее о схеме и прошивке
Если вы захотите модернизировать устройство, вам будет интересно узнать, как оно работает изнутри.
Интерфейс USB использует 4 провода, обозначаемые VCC (питание, +5Вольт), Data- (D-), Data+ (D+), GND (общий провод). Для передачи данных используются линии D+/D-, образующие так называемую «дифференциальную пару». По стандарту, при передаче на одном проводе пары напряжение должно быть не меньше 2,7Вольт, а на другом не больше 0,3Вольт. При приеме уровнем логического нуля считается состояние, в котором напряжение на линии D- не менее чем на 0,2Вольт выше напряжения на линии D+, а уровнем логической единицы — наоборот. Благодаря тому, что в кабеле эти два провода свиты в витую пару, такой протокол обеспечивает высокую помехозащищенность при передаче данных.
Один из проводов из пары подключается ко входу встроенного в МК аналогового компаратора. Это устройство непрерывно сравнивает напряжения на двух своих входах и выдает цифровой сигнал 0 или 1 в зависимости от того, напряжение на каком входе больше. Теоретически, можно было бы подключить к компаратору оба провода пары, но для целей генерации случайного сигнала достаточно одного провода. Ко второму входу подключается внутренний источник опорного напряжения (примерно 1,1Вольт).
Алгоритм работы программы следующий:
1. При включении питания происходит инициализация внутренних устройств МК и портов ввода-вывода (строки 90-134). Порт, используемый для входа компаратора должен всегда быть настроен на ввод без подключения подтягивающего резистора. В противном случае работа USB-интерфейса будет нарушена. После инициализации МК переходит в режим сна, чтобы не тратить зря энергию.
2. Прерывание таймера вызывается с частотой, равной числу возможных значений случайного числа. Благодаря этому периодичность смены значений на индикаторе остается равной 1 секунде независимо от числа значений.
Сразу после включения питания устройство работает в демо-режиме, по очереди отображая все возможные значения по 0,5 секунде каждое (строки 150-171).
Затем происходит переключение в режим начальной инициализации ГСЧ: набор начального значения алгоритмического ГСЧ от физического датчика (строки 173-185).
После инициализации ГСЧ каждое следующее срабатывание таймера приводит к вычислению очередного значения функции ГСЧ и прибавлению младшего бита к случайному значению (строки 187-211). Каждые N циклов (где N равно числу возможных случайных значений) происходит отображение символа, соответствующего случайному значению (подпрограмма DISPLAY_SIGN в подключаемом файле, зависит от числа сегментов), затем текущее случайное значение сбрасывается и цикл начинается сначала.
3. Прерывание аналогового компаратора вызывается каждый раз, когда изменяется его выходное значение (с 0 на 1 или наоборот). Для генерации физического случайного числа используется текущее значение таймера 0, непрерывно считающего с частотой МК (4МГц). Во время начальной инициализации ГСЧ младший бит значения счетчика таймера 0 записывается в младший бит переменной ГСЧ, сдвигая остальные биты в сторону старшего (строки 234-244).
После того, как 32 бита будут набраны, устройство переходит в рабочий режим. В нем значение младших 5 бит счетчика таймера 0 складывается со случайным значением, после чего случайное значение берется по модулю числа возможных значений (строки 247-259).
Для удобства переключения между версиями весь код, данные и константы, зависящие от разрядности индикатора, вынесены в отдельный файл, который включается в основной код. Вы можете создать свой собственный вариант на основе имеющегося.
Соответствие выходов МК и сегментов индикатора обычно выбирают исходя из удобства разводки проводников на плате. В случае, если вы измените схему подключения, вам также придется изменить соответствующую таблицу знакогенератора во включаемом файле. Если используется индикатор с общим анодом (подключенным к +5Вольт), то для зажигания сегмента на выходе МК должен быть 0, если с общим катодом (подключенным к общему проводу), то 1.
Обратите внимание, что в 16-битном варианте реально используются 14 выводов МК, верхняя и нижняя пары сегментов объединены (но каждый подключен через свой резистор). Это может накладывать ограничения на возможности отображения символов. Если вам понадобится разделить эти сегменты, используйте выводы PA0, PA1 (в режиме внутреннего генератора они не используются), изменив подпрограмму DISPLAY_SIGN.
Другие применения
Хотя новые пароли приходится создавать не так уж и часто, описанное устройство может найти другие применения, связанных с генерацией случайных чисел, например вместо кубика в настольных играх. Для удобства работы в различных режимах можно выбрать мышку с дополнительными кнопками и одну из них подключить к МК, доработав прошивку так, чтобы по нажатию этой кнопки переключались таблицы случайных символов или выдавалось следующее случайное число.
Также предложенная схема с минимальными изменениями может быть использована в других устройствах. Первое, что приходит в голову под Новый Год — сделать новогоднюю гирлянду. Для этого вместо индикатора к выходам МК подключаются светодиоды (обычно напряжения 5Вольт хватает на два светодиода, соединенных последовательно, токоограничительные резисторы можно не ставить, если ток через цепочку не будет превышать 20мА), а вместо символов в таблицу знакогенератора записываются комбинации зажигания этих светодиодов. Для подключения цепочек светодиодов большей длины понадобится увеличить напряжение питания (тогда МК нужно будет питать от стабилизатора на 5Вольт) и использовать транзисторные ключи или специализированную микросхему-буфер.
Отдельный вопрос — что делать с физическим датчиком (входом аналогового компаратора). Его можно подключить к проводу достаточной длины (сантиметров 30 должно хватить), сопротивление входа МК весьма высокое и напряжение на входе будет меняться из-за электромагнитных наводок, создавая необходимые случайные импульсы. Если устройство будет питаться от USB (настольный сувенир «мини-елочка»), то вход можно опять же подключить к любой линии данных USB-шины.
