В. И. Ульянова (Ленина) Е. О. Кривоногова ао "Научно-инженерный центр электротехнического университета" (Санкт-Петербург) Алгоритм идентификации вида скремблирования бинарных данных Рассмотрена задача

A  ( x) = S  ( x) G  ( x ) =
I  ( x ) x N  
. G ( x )
+ D  ( x ) G ( x ) =
= I  ( x) x N  + D  ( x ) G ( x ) ,
(4)
б
а

---

rf m
B  ( х ) = S  ( х ) G 2 ( х ) =
= - I ( х ) x N G 2™-1 ( х ) + D ( х ) G 2™ ( х ). 
(5)
Е сли сигнал бы л скрем блирован м ультипли­
кативно, то с учетом ( 1) итогом перем нож ения 
будут полином ы
V  ( х ) = S  ( х ) G  ( х ) = D  ( х ) ,
(6)
F ( х) = S ( х ) G 2™
( х ) = D ( х ) G 2™-1 ( х). 
(7)
Д ля того чтобы принять реш ен ие о виде 
скрем блирования, необходимо проанализировать 
статистические свойства полученны х при де- 
скрем блировании последовательностей. В ы раж е­
ние (4) п редставляет со бой сумму двух полино­
мов. Количество ненулевы х коэф ф ициентов в 
первом полином е не п ревы ш ает степ ен и полино­
м а I  ( х ) и в общ ем случае м ного м еньш е, чем во 
втором слагаем ом полиноме. П оэтом у влияние 
первого полином а н а статистические свойства де- 
скрем блированной 
последовательности 
можно 
считать пренебреж им о малым.
В торое слагаем ое в (4) опи сы вает поток и н ­
ф орм ационны х дан ны х после мультипликативно­
го дескрем блера. В ероятн ость появления ненуле­
вого бита на его выходе в соответствии с [ 1] в 
этом случае составляет
р
 ( A  = 1) =
1 - [ 1 - 2 P (D- = 1 ) J
(8)
где A- - i-й коэф ф ициент полин ом а A ( х ) .
В ы разив правую ч асть (8) ч ерез т , получим 
отклонение вероятн ости P (
= 1) о т 0.5:
т1 = |0.5 - P (Ai = 1)| = ( 2 т / / 2.
(9)
Рассм отри м вы раж ение (5). П ервы й слагае­
м ы й полином не влияет н а статистические свой ­
ства д ескрем блирован ной последовательности, и 
им м ож но пренебречь, есл и количество ненуле­
вы х коэф ф ициентов в нем достаточно мало по 
сравнению со вторы м слагаем ы м . Это условие 
обесп ечивается вы бором значения парам етра m и 
протяж енн ости анализируемого отрезка сигнала.
В торое слагаем ое в (5) опи сы вает поток и н ­
ф орм ационны х данны х, подвергнуты й мульти­
пликативном у д ескрем блирован ию , п ри чем коли­
чество отводов в дескремблере определяется числом
2 m
ненулевы х коэф ф ициентов в G  
( х ). С учетом
12
свойств полиномов над полем G F  (2 ) [6] количе-
2 m
ство ненулевы х коэф ф ициентов в G  
( х ) будет 
равно количеству ненулевы х коэф ф ициентов в 
G ( х ) . С учетом этого свойства отклонени е веро­
ятн о сти P  ( Bi = 1) от 0.5 для данного случая, где
Bi - i-й коэф ф иц иент полином а B ( х ) , состави т
Т2 = Т 1. 
(10)
О братим ся к вы раж ени ям (6) и (7). П ри муль­
типликативном д ескрем блирован ии мультиплика­
тивно скрем блированного си гн ала согласно (6) на 
выходе д ескрем блера сф орм и руется ин ф орм ац и ­
онн ы й сигнал. П р и этом отклонени е вероятн ости 
P ( V  = 1) о т 0.5, где V  - i -й коэф ф ициент поли ­
ном а V  ( х ), состави т
Т3 = т. 
(11)
П р и д ескрем блирован ии с использованием
2 m
полином а G  
( х ) н а выходе д ескрем блера будет 
последовательность, опи сы ваем ая (7), для кото­
р о й отклонение вероятн ости P (F i = 1) от 0.5, где
F - i-й коэф ф ициент полином а F ( х ) , оп ред е­
ли тся как
т4 = |0.5 - P ( F = 1)| = ( 2 т ) V 2, 
(12)
где r - количество ненулевы х коэф ф ициентов в
полином е G 2 
1 ( х ) .
Д ля при няти я р еш ен и я о виде скрем блирова­
ни я необходимо сравнить (9), (10) и (11), (12). Е с­
л и сигнал бы л скрем блирован аддитивно, то в р е ­
зультате дескрем блирован ия с использованием
полином ов G ( х ) и G 2 ( х ) отклонени я вероят­
н о сти будут одинаковыми.
Е сли ж е сигнал был скрем блирован м ульти­
пликативно, то в результате дескрем блирован ия с
использованием полином ов G  ( х ) и G 2 ( х) о т­
клон ен ия вероятн ости будут равны Т3 и Т4 соот­
ветственно, п ри чем Т3 > Т 4 .
Т аки м образом, 
алгоритм идентиф икац ии 
вклю чает следую щ и е операции:
- мультипликативное дескремблирование сигна­
ла с использованием полиномов G ( х ) и G 2™ ( х );
- о ц ен ки отклонени й вероятн ости появления 
ненулевого элем ен та т а и т ь на выходе соответ­
ствую щ их дескрем блеров;

---

Рис. 3
-
различение двух гипотез о виде скрем блера 
по результатам сравнени я полученны х оценок.
А н а л и з р е зу л ь т а т о в м о д е л и р о в а н и я . Н еп о ­
средственное сравнение оц ен ок отклонени й веро­
ятн о сти ненулевого эл ем ен та в дескрем блирован- 
ном сигнале т a и т
ь
является некорректны м. Это 
связано с тем, что полученный набор оценок имеет 
некоторы й разб рос значений, зави сящ и й от объе­
м а анализируем ы х данны х. О птим альное правило 
р азлич ения двух гипотез м ож но сф ормулировать 
только п ри н аличии ин ф орм аци и о значении т. В 
общ ем случае такой ин ф орм аци и нет, что приво­
д и т к необходим ости исп ользован ия эм п и ри ч еск и
вы бранного порога различения.
Определим, насколько различаю тся оценки т a 
и т 
ь
при наихудших для идентификации условиях. 
Одним из таких условий являю тся экстремальные 
значения величины т. В реальны х системах связи 
значение данного параметра зачастую не меньш е
0.01 и не превыш ает 0.4 [1]. Н а рис. 3 приведено 
семейство графиков зависимости отнош ения т ^ т4 
от величины т для разны х значений параметра m.
Из рис. 3 видно, что при т = 0.01 и m = 1 м и ­
ним альное отнош ение оц ен ок равно 50. П ри
С П И С О К Л
1. Cluzeau M. Reconstruction of a Linear Scrambler // 
IEEE Trans. on Computers. 2007. Vol. 56, № 8. P. 1283-1291.
2. Canteaut A., Filiol E. Ciphertext only Reconstruc­
tion of Stream Ciphers Based on Combination Genera­
tors. Berlin: Springer, 2001. 16 p.
3. Johansson T., Jonsson F. Fast Correlation Attacks 
through Reconstruction of Linear Polynomials // Ad­
vances in Cryptology - CRYPTO 2000. 20th Ann. Int. Cryp­
tology Conf. Santa Barbara, Aug. 20-24, 2000. Berlin: 
Springer, 2000. P. 300-315. (Lecture Notes in Computer 
Science 1807).
Статья поступила в редакцию 26 октября 2017 г.