Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

modular inverse operator

A modular inverse operator and modular inverse operation technology, applied in the field of information security, can solve problems such as complex implementation, complex calculation process, and inability to calculate modulo with any non-zero integer, and achieve the effect of reducing hardware power consumption and improving computing efficiency

Active Publication Date: 2019-04-26
SHANGHAI FUDAN MICROELECTRONICS GROUP
View PDF5 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0004] The modular exponentiation algorithm is based on Fermat's little theorem, and converts the modular inversion operation into a modular exponentiation operation, but the modular exponentiation algorithm cannot determine whether the modular inversion result exists
The modular multiplier is used as the hardware operation unit, which is relatively complex and consumes a lot of power
[0005] The extended Euclidean algorithm solves the modular inverse by calculating the greatest common factor by rolling and dividing. When the greatest common factor is a non-1 integer, the calculation result of the modular inverse cannot be obtained
Using the divider as the hardware operation unit, the implementation is still relatively complicated
[0006] The binary extended Euclidean algorithm converts division into shift and addition and subtraction. However, in the process of shifting, the weight of the operand changes, and the final operation result contains 2 n (n is the bit length of the operand) item weight factor, removing the weight factor requires multiple operations of dividing by 2, therefore, the modulus must be an odd number
[0007] The existing binary extended Euclidean algorithm method still has certain limitations in the modular inverse operation, it cannot be used to calculate the modulus for any non-zero integer, and the calculation process is relatively complicated

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • modular inverse operator
  • modular inverse operator
  • modular inverse operator

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0031] The existing binary extended Euclidean algorithm converts division into shift and addition and subtraction. However, in the process of shifting, the weight of operands has changed, and the final operation result contains 2 n (n is the bit length of the operand) item weight factor, the operation of dividing by 2 needs to be performed multiple times to remove the weight factor, therefore, the modulus must be an odd number. However, the existing binary extended Euclidean algorithm method still has certain limitations when performing modular inversion operations, and cannot perform modulo calculations for any non-zero integers, and the calculation process is relatively complicated.

[0032] In the embodiment of the present invention, when the bit length of the first operand X is greater than that of the second operand Y, the redundant sign bit can be eliminated when X is shifted to the left, and the real-time bit length of X is recorded by the variable Xlen, and the weight o...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a modular inverse operation method and an arithmetic device. The modular inversion operation method and the arithmetic device are used for calculating Z=Y<-1>mod X, wherein Z is a result of a modular inverse operation, X is a first operand and Y is a second operand. The modular inverse operation method comprises the following steps of calculating and acquiring a binary bit length Xlen of the first operand X and a binary bit length Ylen of the second operand Y; initializing a first variable R and a second variable S; when Xlen is greater than and equal to Ylen, calculating X <-1>modY; and when Xlen is smaller than and equal to Ylen, calculating Y <-1>modX. When the updated X is equal to 0 and the updated Y is equal to 1, a result of the modular inverse operation is the updated second variable S; when the updated X is equal to 1 and the updated Y is equal to 0, a result of the modular inverse operation is a difference between an X initial value and the updated first variable R; and when one of the updated X and the updated Y is equal to 0 and the other of the updated X and the updated Y is not equal to 1, a result of the modular inverse operation does not exist. By using the method and the arithmetic device, the modular inverse operation, in which the module is any non-zero integer can be realized, the calculation efficiency of the modular inverse operation is improved and the power consumption of hardware is reduced.

Description

technical field [0001] The invention relates to the field of information security, in particular to a modular inverse operation method and a computing device. Background technique [0002] Modular inverse operations are widely used in public key cryptosystems. For example, modular inverse operations are used in the generation of decryption keys in the RSA algorithm. Modular inverse operations can also be used in point addition and point multiplication in elliptic curve cryptographic algorithms. [0003] At present, the methods for solving modular inverse operations mainly include modular exponentiation algorithm, extended Euclidean algorithm, and binary extended Euclidean algorithm. [0004] The modular exponentiation algorithm is based on Fermat's little theorem, and converts the modular inversion operation into a modular exponentiation operation, but the modular exponentiation algorithm cannot determine whether the modular inversion result exists. Using a modular multipli...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F7/72
Inventor 刘凯陆继承赵晓冬王宇
Owner SHANGHAI FUDAN MICROELECTRONICS GROUP
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products