Page 63 - ISCI’2017

For the McEliece scheme, the volumes in Table 1 were estimated by the following. Size of the

open key was estimated as the number of binary elements of the matrix Gx – kn bits. Size of the secret
2
key was estimated as the number of elements of the matrix X (k bits) plus the number of elements,
which need to store permutation rule (nlog2n bits).
The complexity of the encryption was estimated as max number of operations, which need to

execute for forming the code word with the help of matrix calculation of the expression (19). For the
binary (n, k, d)-code it corresponds to k operations XOR over n-bits words. If the calculations are

realized under control of 32(64)-bits operating system, then each n-bits code word presents as a set

of n/32 (n/64) binary words and for a calculation of each from them will need to execute no more k
operations XOR. The complexity of the decryption was estimated as max number of arithmetic

operations over the finite field GF(2 ). These arithmetic operations will need to execute for decoding
m
2
of code word with errors. At the same, the complexity of the decryption was estimated as t . In the
m
practical applications, operations of addition of the elements of the field GF(2 ) are realized by the
operation XOR, and operations of multiplication are realized by tabular method, i.e. through an appeal

2
to the memory cell with a specified input arguments address, so that the assessment t is real.
Resistance assessment of the McEliece code cryptosystem to quantum cryptanalysis was been
executed in the works [46, 47]. In particular, an estimate of the number of iterations to decode

quantum Grover’s algorithm presents in the work [47]. This assessment has the following kind:

n 1
С 2 log n , С = , (21)
1 ( − R) 1 − R

where R = k / n is a relative speed of used code.

The volumes, which presented in Table 1, was calculated by the expression (21). On practice, the
assessment (21) reduces resistance of cryptosystem (approximately twice the equivalent length of the

key is reduced), that, however, it is expected to robust post quantum algorithms (as for the most
symmetric ciphers).

For the cryptosystem RSA, the volumes, which presented in Table 1, was estimated by the following.

A speed of crypto-transformation (encryption and decryption) was estimated as a complexity of
modular exponentiation. Operation of the modular exponentiation, in general case for l-bit numbers,

3
requires about l binary operations. Let p and q are two l-bit simple numbers, transformation
3
2
module (system-wide parameter) is equal to n = pq (2l-bit number), and public (secret) key is 2l-bit

numbers e and d. Then a complexity of modular exponentiation for encryption (decryption) requires

3 2 ( ) l 3 = 12l operations. The most effective is sequential calculation of modular exponentiation my
3
2
modules (p – 1) and (q – 1) respectively. This algorithm requires twice as much number of operations,

63