Page 164 - ISCI’2017

It is necessary to point out that formulae (27) and (28) received for a case, when PRS is produced

by mean of applying only one m -ary symbol. If for producing of PRS µ of m -ary symbols is used
and value of i is getting bigger according to a known rule, then (27) and (28) can be applied to

assessment of cryptographic resistibility of offered PRS generator. If i is getting bigger according to

an unknown rule, then besides it is necessary to solve a task of determination of rule of its changing.
But as we consider that cryptanalyst knows the rule of i changing, (27) and (28) are recommended

for assessment of PRS generators inversion complexity of a type that is observed. In the Table 1 are

given assessments of PRS generator inversion complexity according to (27) and (28). Data analysis
of Table 1 allows making a conclusion that PRS generator inversion complexity has an exponential

character and it is bigger than complexity of «brutal force» method.

Table 1 – Сomplexity of generator inversion

p , p , m
1
Method 2 2048 , 2 1024,
8
128
64
256
128
2 256 , 2 , 2 2 256 , 2 , 2 2 512 , 2 , 2 2 1024 , 2 , 2
256
512
8
2 512
089
500
259
072
172
IKR 5.0543∙10 7.0143∙10 2.1618∙10 1.4827∙10 1.1867∙10
n
096
524
283
196
113
160 6.1103∙10 8.4798∙10 2.6135∙10 1.7925∙10 1.4346∙10
210
111
128
297
ІKRH 256 1.7199∙10 2.3868∙10 7.3562∙10 5.0453∙10 4.0381∙10
538
230
147
316
130
384 3.1726∙10 4.4029∙10 1.3570∙10 9.3071∙10 7.4490∙10
557
249
166
577
149
336
512 5.8524∙10 8.1219∙10 2.5031∙10 1.7168∙10 1.3741∙10

Let us observe one more way to solve a task of PRS generator inversion of the form (20), which
is based on residue classes. For this aim let us give (20) of the following form:
)
b = Θ i x (mod P )(mod P 1 )(mod m ,
i
Θ x i (mod P )(mod P 1 ) q ⋅= i m + b , 0 q ⋅≤ i m + b < P , (29)
1
i
i
0
Θ x i (mod P ) l ⋅= i P + q ⋅ m + b , ≤ l ⋅ P + q ⋅ m + b < P,
i
i
1
i
i
i
1
Θ x i (mod P ) l ⋅= i P + q ⋅ m + b i (mod ) P .
1
i
Direct analysis (29) is showing that x , l i q , are unknown and should be determined. Now let us
i
i
take into account that rule of changing of x is known. On the basis of (29) it is possible to make
i
equation system of the following form:
164