 |
|
Свойства линейной сложности
Пусть 
и 
— двоичные последовательности. Тогда:
1. для любого 
линейная сложность подпоследовательности 
удовлетворяет неравенствам 
;
2. 
тогда и только тогда, когда 
— нулевая последовательность длины 
;
3. 
тогда и только тогда, когда 
;
4. если периодическая с периодом 
, то 
;
5. 
.
[править]Корреляционная независимость
Чтобы получить высокую линейную сложность криптографы пытаются нелинейно объединить результаты нескольких выходных последовательностей. При этом опасность состоит в том, что одна или несколько выходных последовательностей (часто даже выходы отдельных РСЛОС) могут быть связаны общим ключевым потоком и вскрыты с помощью линейной алгебры. Взлом на основе такой уязвимости называют корреляционным вскрытием. Томас Сигенталер показал, что можно точно определитькорреляционную независимость, и что существует компромисс между корреляционной независимостью и линейной сложностью.
Основная идея такого взлома заключается в обнаружении некоторой корреляции между выводом генератора и выводом одной из его составных частей. Затем, наблюдая выходную последовательность, можно получить информацию об этом промежуточном выводе. Используя эту информацию и другие корреляции, можно собирать данные о других промежуточных выводах до тех пор пока генератор не будет взломан.
Против многих генераторов потока ключей на базе регистра сдвига с линейной обратной связью успешно использовались корреляционные вскрытия или из вариации, такие как быстрые корреляционные вскрытия, предполагающие компромисс между вычислительной сложностью и эффективностью.
№ Криптография в стандарте GSM. Алгоритм аутентификации А8 и алгоритм генерации ключа шифрования А3.
Криптография в стандарте GSM. Поточный алгоритм шифрования A5/х.
GSM (от названия группы Groupe Spécial Mobile, позже переименован в Global System for Mobile Communications) (русск.СПС-900) — глобальный стандарт цифровой мобильной сотовой связи, с разделением каналов по времени (TDMA) и частоте (FDMA). Разработан под эгидой Европейского института стандартизации электросвязи (ETSI) в конце 80-х годов.
A8 — алгоритм формирования ключа шифрования, который впоследствии используется для обеспечения конфиденциальности передаваемой по радиоканалу информации в стандарте мобильной сотовой связи GSM. A8 является одним из алгоритмов обеспечения секретности разговора в GSM вместе с A5 и A3. Его задача — генерация сеансового ключа Kc для потокового шифрования информации в канале связи между сотовым телефоном (MS — Mobile Station) и базовой станцией (BTS — Basic Transmitter Station) после аутентификации. По причине безопасности формирование Kc происходит в Sim-карте.