Patent Publication Number: US-8996596-B2

Title: Apparatus and method of generating random number

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority from Korean Patent Application No. 10-2009-0027043, filed on Mar. 30, 2009, in the Korean Intellectual Property Office, the disclosure of which is incorporated herein in its entirety by reference. 
     SUMMARY 
     Methods and apparatuses consistent with the exemplary embodiments relate to data encryption technology, and more particularly, to a random number generation apparatus and a random number generation method by which a random number that constitutes a key for use in encryption can be rapidly and efficiently generated when the key for use in encryption is intended to be generated. 
     According to the related art, a random number generator generates a random number. A random number generated by the random number generator may be used in message encrypting apparatuses, user authentication apparatuses, or the like. For example, when a user encrypts a random number generated by a random number generator by using a public key and transmits the encrypted random number to a server according to an authentication method using a public key, the server decrypts the encrypted random number by using a secret key and authenticates the user to be authentic if a result of the decryption is equal to the random number. 
     Since hard disc drives (HDDs) are able to be randomly accessed, provide a high data transmission speed, are cost-effective, and easily have a larger capacity than other auxiliary storage devices, HDDs have recently been more frequently used to store multimedia data. As the use of HDDs increases, security of data stored in the HDDs becomes an important issue. Accordingly, data stored in HDDs is increasingly subjected to a procedure such as encryption or user authentication. However, when a random number necessary for the encryption or the user authentication is generated, there exists a limit in the speed at which the random number is generated. This limit impedes improvement in the performance of an encryption system or a security system. 
     One or more exemplary embodiments provide a random number generation apparatus and method capable of increasing the speed at which a random number is generated. 
     According to one or more exemplary embodiments, there is provided a random number generation method including the operations of extracting a plurality of digital signals from a storage device; and generating a random number by using the plurality of digital signals. 
     The operation of generating the random number may include the operations of extracting a noise bit from each of the plurality of digital signals; generating a random word by using the noise bit; and sampling the random word at least once to generate the random number. 
     The operation of extracting the noise bit may include extracting the noise bit from a least significant bit of each of the plurality of digital signals. 
     The random number generation method may further include the operations of determining whether the random number is a prime number; and repeating the extracting of the plurality of digital signals, the generating of the random number, and the determining, if the random number is not a prime number. 
     According to one or more exemplary embodiments, there is provided a random number generation apparatus including a signal extraction unit for extracting a plurality of digital signals from a storage device; and a random number generation unit for generating a random number by using the plurality of digital signals. 
     The random number generation unit may include a noise bit extraction unit for extracting a noise bit from each of the plurality of digital signals; a random word generation unit for generating a random word by using the noise bit; and a sampling unit for sampling the random word to generate the random number. 
     The noise bit extraction unit may extract the noise bit from a least significant bit of each of the plurality of digital signals. The sampling unit may sample the random word multiple times to generate the random number. 
     The random number generation apparatus may further include a control unit for controlling the signal extraction unit and the random number generation unit. The control unit may control the signal extraction unit and the random number generation unit to abandon the random number and generate a new random number if the random number is not a prime number. 
     The storage device may be a hard disk drive, and the plurality of digital signals may include a position error signal, a spindle speed error signal, a read channel signal, a temperature signal, the freefall sensor signal, and a shock sensor signal. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Exemplary embodiments will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings in which: 
         FIG. 1  is a graph showing a frequency spectrum component according to noise included in signals existing in a storage device; 
         FIG. 2  is a schematic block diagram of a random number generation apparatus according to an exemplary embodiment; 
         FIG. 3  is a schematic diagram for explaining a random number generation method according to an exemplary embodiment; 
         FIGS. 4A and 4B  are flowcharts of random number generation methods according to exemplary embodiments. 
     
    
    
     DETAILED DESCRIPTION OF THE EXEMPLARY EMBODIMENTS 
       FIG. 1  is a graph showing a frequency spectrum component according to noise included in signals existing in a storage device. 
     Although a hard disk drive (HDD) is illustrated as a storage device in the specification, is the exemplary embodiments are not limited thereto. The exemplary embodiments may be applied to solid state drives (SSDs), non-volatile memories, volatile memories, and optical disk drives (ODDs), etc. 
     In a random number generation method according to an exemplary embodiment, a random number may be generated based on digital signals existing in a storage device (for example, a HDD). A plurality of signals for driving the storage device may exist in the storage device, and each of the signals includes noise. 
     The noise existing in the HDD is close to white noise, and a frequency noise component of the noise may be substantially constant within a frequency band (for example, an audible frequency band). In other words, since a noise component is distributed constantly for each frequency, the noise has good randomness. Consequently, in the random number generation method according to an exemplary embodiment, a random number may be generated based on the noise included in the plurality of signals. 
     As illustrated in  FIG. 1 , a noise component of noise is constantly distributed in a frequency band of about 100 Hz to about 20 KHz. According to this characteristic of the noise, the randomness of a random number may significantly improve. A method or apparatus for generating a random number by using noise according to an exemplary embodiment will now be described in detail with reference to  FIG. 2 . 
       FIG. 2  is a schematic block diagram of a random number generation apparatus  1  according to an exemplary embodiment. Referring to  FIG. 2 , the random number generation apparatus  1  may include a signal extraction unit  20  and a random number generation unit  10 . The signal extraction unit  20  may extract a plurality of digital signals from a storage device. The random number generation apparatus  1  may generate a random number by using various signals existing inside the storage device instead of using external signals. Accordingly, the complexity of the random number generation apparatus  1  may be significantly reduced. 
     For example, if an HDD is described as the storage device, a plurality of signals that can be extracted from the HDD by the signal extraction unit  20  may include at least one of a position error signal, a spindle speed error signal, a read channel signal, a temperature signal, a freefall sensor signal, and a shock sensor signal. Each of these signals may include noise having the above-described characteristics. 
     The position error signal may be output from a servo block of a read channel chip and may correspond to the track off degree of a data readout head. The spindle speed error signal may be output from a spindle motor and may correspond to an error value of a spindle speed. The read channel signal may be output from a data block of the read channel chip, and the temperature signal may be output from a preamplifier. The freefall sensor signal may be output from a freefall sensor, and the shock sensor signal may be output from a shock sensor. 
     The above-described signals may be digitalized and used within the HDD. In this case, the signal extraction unit  20  may extract a plurality of digital signals obtained by digitalization from the storage device and transmit the digital signals to the random number generation unit  10 . 
     In some exemplary embodiments, the above-described signals may be extracted in the form of analog signals. In this case, the signal extraction unit  20  may further include an analog-digital conversion unit (not shown) for converting the extracted analog signals into digital signals. 
     The random number generation unit  10  may include a noise bit extracting unit  11 , a random word generating unit  12 , and a sampling unit  13 . 
     The noise bit extracting unit  11  may extract a noise bit NB from each of the plurality of digital signals output by the signal extraction unit  20 . In more detail, a noise component may be included in a signal existing in the storage device. In general, the amplitude of the noise component is much smaller than the amplitude of a signal from which the noise has been excluded. For example, if a signal to noise ratio (SNR) is about 40 dB, the amplitude of the signal is about 100 times greater than that of the noise included in the signal. Thus, when such a signal is converted into a digital signal, a noise component occupies a significantly small weight on the digital signal. 
     In other words, if an arbitrary signal existing in the storage device is digitalized, the noise bit extracting unit  11  may consider a least significant bit (LSB) of a digital signal obtained by the digitalization as the noise bit NB. Accordingly, the noise bit NB is expressed as in Equation 1.
 
NB(=Noise Bit)=LSB(Digital Signal)  [Equation 1]
 
     Since the noise bit extracting unit  11  extracts only an LSB from a digital signal and determines the LSB as the noise bit NB, the noise bit NB may have a 1-bit length. 
     In an exemplary embodiment, a random number is generated using a plurality of digital signals, and thus this noise bit extraction may be equally applied to all of the signals in the plurality of digital signals. Thus, when noise bits are extracted using a plurality of digital signals, the noise bits are expressed as in Equation 2. 
     
       
         
           
             
               
                 
                   
                     
                       NB_ 
                       ⁢ 
                       1 
                     
                     = 
                     
                       LSB 
                       ⁡ 
                       
                         ( 
                         
                           Digital 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           Signal_ 
                           ⁢ 
                           1 
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       NB_ 
                       ⁢ 
                       2 
                     
                     = 
                     
                       LSB 
                       ⁡ 
                       
                         ( 
                         
                           Digital 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           Signal_ 
                           ⁢ 
                           2 
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   ⋮ 
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     NB_N 
                     = 
                     
                       LSB 
                       ⁡ 
                       
                         ( 
                         
                           Digital 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           Signal_N 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Equation 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
     Equation 2 relates to extraction of N noise bits NB_ 1  through NB_N from N digital signals, respectively, and the random word generating unit  12  may generate a random word RW by using the noise bits NB_ 1  through NB_N output from the noise bit extracting unit  11 . 
     The noise bits NB_ 1  through NB_N are synthesized to generate the random word RW using Equation 3.
 
RW(Random word)=[NB — 1 NB — 2 . . . NB_N]  [Equation 3]
 
     The plurality of digital signals are all independent from one another and have no correlations with one another, and thus the randomness between the noise bits NB_ 1  through NB_N may be greatly increased. The length of the random word RW is equal to the number of digital signals used in the synthesis (for example, N bits). Accordingly, as the number of digital signals used in random number generation increases, the size of the random word RW may increase. 
     The random word RW output from the random word generating unit  12  may be transmitted to the sampling unit  13 . The sampling unit  13  may generate a final random number RN by performing a sampling operation on the random word RW at least one time. In more detail, the length of a random number for generating a key for use in data encryption or user authentication needs to be the same as a key length of an algorithm, but if the length (for example, N bits) of the random number generated by the random word generating unit  12  is less than the key length, the sampling unit  13  may generate a random number corresponding to the key length by sampling the random word RW a plurality of number of times. The random number RN output from the sampling unit  13  may be transmitted to an encryption key generation unit  2 . The encryption key generation unit  2  may generate an encryption key necessary for data encryption on the basis of the received random number RN. 
     The sampling operation may be performed a plurality of number of times at different timings by the sampling unit  13 . Accordingly, randomness may be secured between a plurality of random words. The plurality of sampling operations performed by the sampling unit  13  are expressed as in Equation 4.
 
RN(Random Number)=[RW(n=1)RW(n=2) . . . RW(n=M)]  [Equation 4]
 
where n denotes the number of times of sampling operations performed. In Equation 4, an M number of times of sampling operations are performed, and the random number RN has a length of a total of n×M bits.
 
     For example, when a random number having a 256-bit length is desired to be generated, if only one digital signal is used, the random word RW has a 1-bit length, and thus 256 sampling operations may be required to generate one random number. 
     However, since a random number may be generated by using a plurality of digital signals (for example, 8 digital signals) based on a random number generation method according to an exemplary embodiment, the random number may be generated when the random word RW has a 8-bit length and only 32 (=256/8) sampling operations are performed. In other words, the speed at which a random number is generated may increase in proportion to the number of digital signals used in random number generation. 
     In a random number generation method according to another exemplary embodiment, the noise bit extracting unit  11  may extract the LSB and an LSB−1 previous to the LSB from each of the plurality of digital signals to serve as the noise bit NB. In this case, the randomness of the noise bit NB may somewhat degrade, but the length of the random word RW may increase. Thus, the random number generation speed may increase more than in the random number generation method according to the previous exemplary embodiment, in which only the LSB of each digital signal serves as the noise bit NB. 
     Although the position error signal, the spindle speed error signal, the read channel signal, the temperature signal, the freefall sensor signal, and the shock sensor signal are described as the signals used in random number generation, they are just examples. In other words, the signals used in random number generation may include all signals that exist in the HDD and include noise. 
     The random number generation apparatus  1  may further include a control unit  30 . When an encryption algorithm according to an exemplary embodiment is a Rivest-Shamir-Adleman (RSA) algorithm, the random number RN output from the random number generation unit  10  may be used as an encryption key only when the random number RN is a prime number. 
     Accordingly, the random number generation apparatus  1  which may be driven according to the RSA algorithm may further include the control unit  30 . The control unit  30  may determine whether the random number RN output from the sampling unit  13  is a prime number. If it is determined that the random number RN output from the sampling unit  13  is not a prime number, the control unit  30  may control the signal extraction unit  20  and the random number generation unit  10  to abandon (or discard) the output random number RN and generate a new random number. On the other hand, if it is determined that the random number RN output from the sampling unit  13  is a prime number, the random number RN may be used to generate the encryption key. 
     Since the random number RN output from the sampling unit  13  is implemented as a digital value, the control unit  30  may further perform a process of converting the random number RN with a digital value output from the sampling unit  13  into a decimal natural number. Thus, the control unit  30  may determine whether a decimal random number obtained by the conversion is a prime number. 
       FIG. 3  is a schematic diagram for explaining a random number generation method according to an exemplary embodiment. Referring to  FIGS. 2 and 3 , the noise bit extracting unit  11  may extract the noise bit NB from each of the plurality of signals, for example, a first digital signal Signal  1  through to an N-th digital signal Signal N. As illustrated in  FIG. 3 , the noise bit extracting unit  11  may extract the LSB of each of the first digital signal Signal  1  through to the N-th digital signal Signal N as the noise bit NB and transmit the noise bits NB to the random word generating unit  12 . 
     For example, the first digital signal Signal  1  may have a digital value of ‘0111 . . . 0100’, and the noise bit extracting unit  11  may extract the LSB of ‘0’ from the digital value and determine the LSB as the noise bit NB. Similarly, the second digital signal Signal  2  may have a digital value of ‘1001 . . . 0011’, and the noise bit extracting unit  11  may extract the LSB of ‘1’ from the digital value and determine the LSB as the noise bit NB. 
     In other words, the noise bit extracting unit  11  extract the noise bit NB from each of the first digital signal Signal  1  through the N-th digital signal Signal N. The noise bits NB extracted from the first through N-th digital signals Signal  1 -Signal N may be transmitted to the random word generating unit  12 . At this time, the noise bits NB may be random because the digital signals are independent from one another and random as described above. 
     The random word generating unit  12  may generate the random word RW by using the noise bits NB extracted by the noise bit extracting unit  11 . As illustrated in  FIG. 3 , the random word RW may have an N-bit length, and the bits that constitute the random word RW may correspond to the LSBs of the first through N-th digital signals Signal  1 -Signal N. 
     The sampling unit  13  may sample, at least one time, the random word RW output by the random word generating unit  12  to generate the random number RN. For example,  FIG. 3  illustrates a process of generating a random number by performing a sampling operation on the random word RW M times at different timings, and thus the random number may have a N×M-bit length. 
       FIGS. 4A and 4B  are flowcharts of random number generation methods according to exemplary embodiments.  FIG. 4A  is a flowchart of a random number generation method based on a general encryption algorithm. Referring to  FIGS. 2 through 4A , in operation S 405 , the signal extraction unit  20  may extract the plurality of digital signals from the storage device. In operation S 410 , the noise bit extracting unit  11  may extract the noise bit NB from each of the plurality of digital signals. As described above, the noise bit NB may correspond to the LSB of each of the digital signals. 
     In operation S 415 , the random word generating unit  12  may generate a random word RW based on the noise bits NB. In operation S 420 , the sampling unit  13  may sample the random word RW at least one time to generate the random number RN. 
       FIG. 4B  is a flowchart of a random number generation method based on the RSA encryption algorithm. Referring to  FIGS. 2 through 4B , in operation S 505 , the signal extraction unit  20  may extract the plurality of digital signals from the storage device. In operation S 510 , the noise bit extracting unit  11  may extract the noise bit NB from each of the plurality of digital signals. As described above, the noise bit NB may correspond to the LSB of each of the digital signals. 
     In operation S 515 , the random word generating unit  12  may generate a random word RW based on the noise bits NB. In operation S 520 , the sampling unit  13  may sample the random word RW at least one time to generate a random number RN. In operation S 525 , the control unit  30  may determine whether the random number RN is a prime number. If it is determined that the random number RN is a prime number, the random number RN may be used as the encryption key. If it is determined that the random number RN is not a prime number, the control unit  30  may control the signal extraction unit  20  and the random number generation unit  10  to abandon (or discard) the random number RN and generate a new random number. 
     In a random number generation method or apparatus according to an exemplary embodiment, the speed at which a random number is generated may be significantly increased. In addition, in the random number generation method or apparatus according to one or more exemplary embodiments, the performance of a security system or an encryption system for a storage device may significantly improve. 
     The exemplary embodiments can also be embodied as computer readable codes on a computer readable recording medium. The computer readable recording medium is any data storage device that can store data which can be thereafter read by a computer system. Examples of the computer readable recording medium include read-only memory (ROM), random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, optical data storage devices, etc. The computer readable recording medium can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion. 
     While various exemplary embodiments been particularly shown and described, it will be understood that various changes in form and details may be made therein without departing from the spirit and scope of the following claims.