Kovtun M. Methods of implementation of high speed arithmetic operations in fields, rings and algebraic curves for cryptographic applications

Thesis is devoted to solving the actual scientific and technical problem of speed-up information and telecommunication systems of the certification authority in National Electronic Digital Signature System for DSTU 4145-2002, ECDSA, RSA without significant financial costs. Speed-up of digital signature operations are in reducing the time of a labor-intensive scalar multiplication operation. The method of dividing large integers of single and double precision based on the school division algorithm is improved. This allows to speed-up of common parameters generation for the RSA cryptosystem. Extracting of n -root method as an example of a cubic root is improved. This allows to speed-up of searching birationally equivalent Edwards curves to Weierstrass curves from DSTU 4145-2002 and recommended by NIST FIPS 186-3 in a binary field. Multiplicative inversion method in a binary field is improved. First proposed method of algorithm building for modular reducing by irreducible polynomial (trinomial, pentanomial) was developed. This allows the constructing of algorithms for various target platforms. Scalar multiplication method in the points group is improved by using birationally equivalent Edwards curves, which allowed to speed-up duration of creation and verification of digital signature in accordance with DSTU 4145-2002 and ECDSA. All proposed methods in dissertation thesis are implemented in library of cryptographic primitives “Cipher+”.