Browse Prior Art Database

A Method to Reduce Encryption Time Using Fast Path for Chinese Remainder Theorem (CRT) Operation in Cryptography

IP.com Disclosure Number: IPCOM000016343D
Original Publication Date: 2002-Dec-22
Included in the Prior Art Database: 2003-Jun-21
Document File: 2 page(s) / 45K

Publishing Venue

IBM

Abstract

Disclosed is a Fast Path for Chinese Remainder Theorem (CRT) Operation used by cryptography. The Normal Path CRT Operation is a six-step process and involves many iterations of many mathematical operations using very large numbers. As a result, the Normal Path CRT Operation takes a long time to complete. However, if a software is encrypting records in a large database, there is a high probability that many records would have some fields that contain all zeros. If the Normal Path CRT Operation is used to calculate the output message when the input message contains all zeros, then it can still take a long time to calculate the output message. On the other hand, if the Fast Path CRT Operation is used to calculate the output message when the input message contains all zeros, then the Normal Path CRT Operation can be bypassed completely and the output message can be calculated very quickly using only one check and an assignment of all zeros. The Fast Path CRT Operation states that if the input message contains all zeros, the output message is also all zeros. Figure 1 shows how an input message is encrypted using either the Normal Path CRT Operation or the Fast Path CRT Operation based on the input message data. If the input message (m) contains all zeros, then the Fast Path CRT Operation is performed. Otherwise, Normal Path CRT Operation is performed. The input message for Fast Path CRT Operation can be part of a record, an entire record, two adjacent records that contain zeros at the end of first record and at the beginning of second record, or multiple records. START END

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

  A Method to Reduce Encryption Time Using Fast Path for Chinese Remainder Theorem (CRT) Operation in Cryptography

    Disclosed is a Fast Path for Chinese Remainder Theorem (CRT) Operation used by cryptography. The Normal Path CRT Operation is a six-step process and involves many iterations of many mathematical operations using very large numbers. As a result, the Normal Path CRT Operation takes a long time to complete. However, if a software is encrypting records in a large database, there is a high probability that many records would have some fields that contain all zeros. If the Normal Path CRT Operation is used to calculate the output message when the input message contains all zeros, then it can still take a long time to calculate the output message. On the other hand, if the Fast Path CRT Operation is used to calculate the output message when the input message contains all zeros, then the Normal Path CRT Operation can be bypassed completely and the output message can be calculated very quickly using only one check and an assignment of all zeros. The Fast Path CRT Operation states that if the input message contains all zeros, the output message is also all zeros.

Figure 1 shows how an input message is encrypted using either the Normal Path CRT Operation or the Fast Path CRT Operation based on the input message data. If the input message (m) contains all zeros, then the Fast Path CRT Operation is performed. Otherwise, Normal Path CRT Operation is performed. The input message for Fast Path CRT Operation can be part of a record, an entire record, two adjacent records that contain zeros at the end of first record and at the beginning of second record, or multiple records.

START

END

NOYES m = 0?

Figure 1. An Input Message Encryption Process Using CRT Operations.

Since the goal is to minimize the encryption time using the Fast Path CRT Operation, one or more input records should be segmented such that each segment contains a block of contiguous zeros or a block of contiguous non-zeros. Also, the length of each segment must not exceed the maximum length of the input message. Each segment is then used as an input message, and each input message (m) is encrypted separately using the CRT Operation shown in Figure 1 to obtain the encrypted output message
(t.) Also, each...