Written in x86 assembly language using the Flat Assembler (FASM), this program generates the large prime numbers that are required for the Digital Signature Algorithm (DSA).
The DSA primes p and q are two large prime numbers, which satisfy the relation:
p mod q = 1
In other words, q is a prime factor of p-1.
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is outlined in chapter 4 of the Digital Signature Standard (DSS), as published by the U.S. National Institute of Standards and Technology:
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
The actual mathematical details for the DSA are specified in the fips 186-3 appendices.
In the DSA, a digital signature is generated by applying a private key (x) to the hash of the message to be signed. A public key (y) is used for verification of the signature. The keys x and y are generated from the domain parameters {p, q, g}. The DSA is based on the ElGamal signature scheme.
In this project, the only parts of the DSA I implement are those related to the generation of the two large prime numbers q and p. I do not compute the generator g, the keys x and y, or implement the actual signature process.
These are the parameters output by my program:
| Small Prime c | The starter prime of less than 33 bits in length used to generate the prime q. |
| Small Prime c0 | The starter prime of less than 33 bits in length used to generate the prime p0. |
| First Seed | The initial value of the seed for the hash function. |
| Q Seed | The value of the hash function seed at the time the prime q was found. |
| P0 Seed | The value of the hash function seed at the time the prime p0 was found. |
| P Seed | The value of the hash function seed at the time the prime p was found. |
| Qgen Counter | The value of the counter at the time the prime q was found. |
| P0gen Counter | The value of the counter at the time the prime p0 was found. |
| Pgen Counter | The value of the counter at the time the prime p was found. |
| Q | The prime q, with a bit length as given by N. |
| P0 | The prime p0, the starter prime for p. |
| P | The prime p, with a bit length as given by L. |
The various seed and counter values allow the primes q and p to be verified, since a particular first seed will always generate the same set of prime numbers and their corresponding seed and counter values.
To generate these numbers, I implement the following sections from FIPS 186-3:
| A1.2 | Construction and Validation of the Provable Primes p and q. |
| C.2 | Conversion Between Bit Strings and Integers. |
| C.6 | Shawe-Taylor Random_Prime Routine. |
| C.7 | Trial Division. |
| C.8 | Sieve Procedure. |
The Keys x and y
I don’t implement the key generation process in my code, but I will briefly discuss it. The private key x is a randomly generated integer value in the range [1,q-1]. The public key y is in the range [1,p-1]. It is calculated from x:
y(x)=gx mod p
The only unknown in the expression above is the private key x, all of the other parameters are publically available. So how does the value of x remain secret? The security of x depends on the well known discrete logarithm problem. Here x is the discrete logarithm (to base g) of y. Currently there is no known method to quickly compute discrete logarithms, and a brute force approach to find x is out of the question because of the size of the DSA primes. Therefore y(x) is basically a one way function.
DSA Security Strength
There are two factors which determine the security strength (or bit strength) of the DSA signature process. The first is the size of the primes p and q, and the second is the choice of hash function used to hash the seed.
The DSA length parameters (L,N) define the size of the two primes, where L is the bit length of p and N is the bit length of q. These are restricted to certain values by the DSS.
The DSS also specifies which hash algorithms can be used in the DSA (the SHA algorithms). Not only is the hash function used to generate the signature for a particular message M, but it is also used to generate the primes p and q.
NIST Special Publication 800-57 (SP 800-57 Part 1) provides some information on the security strengths for the (L,N) pair and hash algorithms. See tables 2 and 3 on pages 63 and 64:
http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57-Part1-revised2_Mar08-2007.pdf
The DSS recommends that the security strength of the hash function either match or exceed that of the selected (L,N) pair. In my program I have chosen the hash functions such that they equal the security strength of each (L,N) pair.
The table shows which combinations of (L,N), SHA functions and seed lengths are supported by my program:
| L | N | Hash() | Bits of Security | Seed Length |
|---|---|---|---|---|
| 1024 | 160 | SHA-1 | 80 | 160 bits |
| 2048 | 224 | SHA-224 | 112 | 224 bits |
| 2048 | 256 | SHA-256 | 128 | 256 bits |
| 3072 | 256 | SHA-256 | 128 | 256 bits |
Seeds and Counters
The generation process requires an initial seed value known as the first seed. The hash function is applied to this seed at various points during the prime generation process, to construct starter values for each of the primes. Every time the hash function is used in this way, the seed value is incremented by 1. The value of the first seed can either be set by the user or be randomly generated.
The DSS requires that the bit length of the seed has to be at least equal to N, the bit length of the prime q. In my code I set the length of the seed equal to N bits, as can be seen in the table above.
The generation process also uses a counter, which is initialised to zero. This counter is incremented every time a new candidate prime is generated, and when a candidate is confirmed to be prime the value of the counter is saved.
Using the seed and counter method to generate p and q allows an end user to verify that these values are legitimate. They just take the supplied first seed value and apply the same calculations to it.
Generating q
The method defined in Appendix C.6 (Shawe-Taylor Random_Prime Routine) is used to construct the primes q and p0. There are two parts to this method. Steps 3-13 are used to generate a starter prime of less than 33 bits in length, by repeatedly hashing the seed until a value is obtained that is confirmed to be prime. The sieve procedure outlined in Appendix C.8 is used to test the candidates for this small prime. This method is basically the Sieve of Eratosthenes, an algorithm for testing primes that dates back to Ancient Greece.
Steps 16-34 make up the second part of the method.
Note that the method is recursive. If the input length is greater than 32 bits, the method jumps to step 14 where it calls itself again (but with approx half the length). Once the length is less than 33 bits, steps 3-13 of the algorithm are executed to generate the initial starter prime. Then for each time the method was called at step 14, steps 16-34 are executed.
So for example, if N = 160 the flow of execution looks like this:
ST_Random_Prime(160) - Length greater than 32, jump to step 14. ST_Random_Prime(81) - Length greater than 32, jump to step 14. ST_Random_Prime(42) - Length greater than 32, jump to step 14. ST_Random_Prime(22) - Execute steps 3-13 to get c0 and return. ST_Random_Prime(42) - Execute steps 16-34 and return the next c0. ST_Random_Prime(81) - Execute steps 16-34 and return the next c0. ST_Random_Prime(160) - Execute steps 16-34 and return q. |
Steps 16-34 use the input prime c0 to construct a larger prime c, as follows:
The seed is hashed again to produce a string of random bits (x) which is then adjusted so that it has a bit length equal to the input length.
A parameter t is then calculated from x using c0:
t = ceiling(x/2c0)
An initial candidate value for the prime c is then defined as:
c = 2tc0 + 1
This candidate value is then tested for primality. If it is not prime, then the value of t is incremented (t = t + 1), and c is recalculated:
c’ = 2(t + 1)c0 + 1 = c + 2c0
This procedure is repeated until a value of c is found that is prime.
Generating p
The process specified in Appendix A1.2 (Construction and Validation of the Provable Primes p and q) is used to construct the largest prime p. The primes q and p0 are used to construct candidates for p as follows:
p = 2tqp0 + 1
Using q in this way guarantees that q will be a prime factor of p-1, as required.
As for the case of q above, successive candidate values are generated until a prime is obtained:
p’ = 2(t + 1)qp0 + 1 = p + 2qp0
Testing Primality
To test the primality of the candidate primes in the construction process for p and q, the DSA uses the Pocklington-Lehmer Primality Test. For some random integer a, this test guarantees that a number N will be prime if it satisfies the following conditions:
aN-1 mod N = 1
GCD(a(N-1)/p – 1,N) = 1
– where p is a prime factor of N-1.
The DSA generates a random integer a (with a bit length of at least N bits) to test candidates for the prime q, by using the same method that was used to generate x (above). This value is then adjusted so that it is in the range [2,c-2]:
a = 2 + [ a mod (c-3) ]
To test candidates (c = 2tc0 + 1) for the prime q (and p0), the DSA computes a parameter:
z = a2t mod c
It then tests the condition:
GCD(z-1,c) = 1
Since 2t = (c-1)/c0, this is the same as the GCD part of the Pocklington-Lehmer Primality Test.
The DSA then tests the condition:
zc0 mod c = 1
But since:
zc0 = (a2t)c0 = (a(c-1)/c0)c0 = ac-1
– this test is the same as:
ac-1 mod c = 1
For candidates of the prime p, the DSA applies the following tests (for z = a2tq mod p):
GCD(z-1,p) = 1
zp0 mod p = 1
Again it can be shown that this is just the Pocklington-Lehmer Primality Test.
Fast Exclusion Of Non-Primes
To test the candidates for the primes p and q, the DSA uses the Pocklington-Lehmer Primality Test. However, this test requires the use of exponentiation which takes a lot of processing time. Therefore I have introduced an additional step in the testing process, which is not specified in the DSA. The aim of this extra step is to quickly prove that the candidate is not a prime. By doing this the need to carry out the exponentiation can be avoided, thus speeding up the search process for the primes p and q.
To quickly prove that a candidate is non-prime, I just generate some random numbers and use the GCD function to determine if they are coprime (i.e. GCD = 1) with the candidate. If even one of these random numbers is not coprime with the candidate, then the candidate value is not a prime and can be rejected. Quite a few random numbers are needed for this test, because it has been found that any random pair of numbers are likely to be coprime about 60% of the time. Further more, it turns out that some of the candidates generated by the DSA are testing coprime with over 95% of the random values. To make sure that these candidates can be eliminated, I generate 50 random values for testing. This test will not exclude all non-primes because some of the candidates test coprime against 100% of the random values (even if there are a 1000 randoms being generated).
By applying the above test, I can quickly reject about 70-80% of the candidate primes and save a large amount of processing time. For example, the exponentiation computation to test the candidate for p0 (where L = 1024 and L0 = 513) takes about 2 seconds. It would normally take 20 seconds to test 10 candidates in this way, but by applying the GCD filter this time can be reduced to about 4-6 seconds. The time savings are even greater for the larger primes. The exponentiation to test the candidate for p (L = 1024) takes about 6 seconds. Considering that hundreds or even thousands of candidates (up to the limit of 4 x L specified by the DSA) may need to be tested before a value for the prime p is found, the reduction in processing time can be quite significant.
How To Hash The Seed
In the DSA, the SHA hash functions are applied to the seed to generate pseudo-random starter values for the primes p and q. The seed and the starter values are integers, but the inputs and outputs for the SHA functions are bit strings. Therefore conversion between bit strings and integer values is required (as discussed in Appendix C.2).
The byte order in the seed integer value is little endian. To convert this to a message (bit string) that can be hashed, the bytes are reversed such that the byte order becomes big endian. The SHA 1, 224 and 256 algorithms process a message in blocks of 512 bits. Since the maximum length of the seed is 256 bits, it only requires a single 512 bit block as the input to the hash function. This block is in big endian byte order, with the first 160, 224 or 256 bits being the seed. The remaining bits in the block are the padding bits. These are all zero, with the exception of the first bit following the message (the seed) which is set to 1, and the last 16 bits which are set to the length of the message (the seed length).
The SHA functions output the result as an array of 32 bit words:
H[0]H[1]H[2]H[3]H[4] – e.g. for SHA-1.
This output is converted to a number, just by reversing the array indexing (e.g. H[4] becomes H'[0] etc):
H'[4]H'[3]H'[2]H'[1]H'[0]
It is this form of the hash output that is used to generate the pseudo-random starter values for the candidate primes.
Program Speed
The program uses a lot of processing power, so it can take a while to generate the primes. For L = 1024, the program should be able to generate some primes in less than 30 minutes (on a decent machine). For L = 2048 and L = 3072, it can take up to a couple of hours (or longer) to generate the primes.
Test Vectors
A zip file containing test vectors can be found on the NIST website. It is called: 186-3dsatestvectors.zip
Usage
The program allows the primes to be generated either all at once, or one at a time.
To generate all of the primes at once, press the [Generate All] button. Note that it can take up to one or two hours for a result to be returned.
To generate the primes one at a time (in sequence), first press the [Generate q] button to compute q. Once q has been found, press [Generate p0] to compute the prime p0. Finally, press [Generate p] to find the prime p. The program only takes a couple of minutes to find q, up to 30 minutes to find p0, and one or two hours to find p.
Of course, before generating any primes the L,N pair should be selected by pressing the appropiate button.
After the L,N pair has been set, the user may optionally enter a value for the first seed and press the [Capture] button to get this value. If a first seed value is not supplied in this way, a random value for the first seed will be internally generated by the program.
The FASM x86 Code
To grab this code, select it with the mouse and copy it. It can then be pasted directly into the FASM IDE.
; -------------------------------------------------------------------------------------
format PE GUI 4.0
entry start
include 'win32a.inc'
; -------------------------------------------------------------------------------------
IDD_THE_DIALOG = 102
IDC_CAPTURE = 1000
IDC_GEN_Q = 1001
IDC_GEN_P0 = 1002
IDC_GEN_P = 1003
IDC_GEN_ALL = 1004
IDC_START_OVER = 1005
IDC_TOGGLE = 1006
IDC_OUTPUT = 1007
IDC_FIRST_SEED = 1008
IDC_BTN_1024_160 = 1009
IDC_BTN_2048_224 = 1010
IDC_BTN_2048_256 = 1011
IDC_BTN_3072_256 = 1012
; -------------------------------------------------------------------------------------
HEX_LEN = 400
DBL_HEX_LEN = 2*HEX_LEN
BF_DISP_LEN = 6000
; -------------------------------------------------------------------------------------
section '.code' code readable executable
start:
invoke GetModuleHandle,0
invoke DialogBoxParam,eax,IDD_THE_DIALOG,0,DialogProc,0
exit:
invoke ExitProcess,0
; -------------------------------------------------------------------------------------
proc DialogProc uses esi edi ebx,hwnddlg,msg,wparam,lparam
cmp [msg],WM_INITDIALOG
je .wminitdialog
cmp [msg],WM_COMMAND
je .wmcommand
cmp [msg],WM_CLOSE
je .wmclose
xor eax,eax
jmp .quit
.wminitdialog:
invoke SetDlgItemText,[hwnddlg],IDC_FIRST_SEED,""
stdcall CalcSieve
stdcall PrintDomainParameters
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.wmcommand:
cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_1024_160
je .1024_160
cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_2048_224
je .2048_224
cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_2048_256
je .2048_256
cmp [wparam], BN_CLICKED shl 16 + IDC_BTN_3072_256
je .3072_256
cmp [wparam], BN_CLICKED shl 16 + IDC_CAPTURE
je .CAPTURE
cmp [wparam], BN_CLICKED shl 16 + IDC_GEN_Q
je .GENERATE_Q
cmp [wparam], BN_CLICKED shl 16 + IDC_GEN_P0
je .GENERATE_P0
cmp [wparam], BN_CLICKED shl 16 + IDC_GEN_P
je .GENERATE_P
cmp [wparam], BN_CLICKED shl 16 + IDC_GEN_ALL
je .GENERATE_ALL
cmp [wparam], BN_CLICKED shl 16 + IDC_START_OVER
je .START_OVER
cmp [wparam], BN_CLICKED shl 16 + IDC_TOGGLE
je .TOGGLE_VIEW
jmp .done
.1024_160:
mov [DSA_N],word 160
mov [DSA_L],word 1024
stdcall PrintDomainParameters
mov [bToggle],byte 0
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.2048_224:
mov [DSA_N],word 224
mov [DSA_L],word 2048
stdcall PrintDomainParameters
mov [bToggle],byte 0
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.2048_256:
mov [DSA_N],word 256
mov [DSA_L],word 2048
stdcall PrintDomainParameters
mov [bToggle],byte 0
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.3072_256:
mov [DSA_N],word 256
mov [DSA_L],word 3072
stdcall PrintDomainParameters
mov [bToggle],byte 0
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.CAPTURE:
invoke GetDlgItemText,[hwnddlg],IDC_FIRST_SEED,bfDisplay,BF_DISP_LEN
stdcall ReadFirstSeed
stdcall PrintFirstSeed
invoke SetDlgItemText,[hwnddlg],IDC_FIRST_SEED,bfDisplay
jmp .done
.GENERATE_Q:
stdcall Generate_q
cmp al,0
je .ERROR
stdcall Print_q_Found
mov [bToggle],byte 1
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.GENERATE_P0:
stdcall Generate_p0
cmp al,0
je .ERROR
stdcall Print_p0_Found
mov [bToggle],byte 1
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.GENERATE_P:
stdcall Generate_p
cmp al,0
je .ERROR
stdcall Print_p_Found
mov [bToggle],byte 1
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.GENERATE_ALL:
stdcall Generate_q
cmp al,0
je .ERROR
stdcall Generate_p0
cmp al,0
je .ERROR
stdcall Generate_p
cmp al,0
je .ERROR
stdcall Print_pq_Found
mov [bToggle],byte 1
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.START_OVER:
stdcall StartOver
invoke SetDlgItemText,[hwnddlg],IDC_FIRST_SEED,""
stdcall PrintDomainParameters
mov [bToggle],byte 0
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.TOGGLE_VIEW:
cmp [bToggle],byte 0
je .TOGGLE_1
stdcall PrintDomainParameters
mov [bToggle],byte 0
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.TOGGLE_1:
stdcall PrintLastCandidate
mov [bToggle],byte 1
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.ERROR:
stdcall PrintError
invoke SetDlgItemText,[hwnddlg],IDC_OUTPUT,bfDisplay
jmp .done
.wmclose:
invoke EndDialog,[hwnddlg],0
.done:
mov eax,1
.quit:
ret
endp
; -------------------------------------------------------------------------------------
macro PRINT_CRLF
{
mov [edi],byte 13
inc edi
mov [edi],byte 10
inc edi
}
; -------------------------------------------------------------------------------------
proc PrintDomainParameters
; print the domain parameters
lea edi,[bfDisplay]
; N (length of p)
mov [edi],dword "N = "
add edi,4
mov ax,[DSA_N]
stdcall HexToDec
mov [edi],dword " "
add edi,4
; L (length of q)
mov [edi],dword "L = "
add edi,4
mov ax,[DSA_L]
stdcall HexToDec
PRINT_CRLF
PRINT_CRLF
; small prime c
mov [edi],dword "Smal"
add edi,4
mov [edi],dword "l Pr"
add edi,4
mov [edi],dword "ime_"
add edi,4
mov [edi],dword "c: "
add edi,4
mov eax,[Prime_c]
stdcall DWordToStr
PRINT_CRLF
PRINT_CRLF
; small prime c0
mov [edi],dword "Smal"
add edi,4
mov [edi],dword "l Pr"
add edi,4
mov [edi],dword "ime_"
add edi,4
mov [edi],dword "c0: "
add edi,4
mov eax,[Prime_c0]
stdcall DWordToStr
PRINT_CRLF
PRINT_CRLF
; q gen counter
mov [edi],dword "q_ge"
add edi,4
mov [edi],dword "n_co"
add edi,4
mov [edi],dword "unt:"
add edi,4
mov [edi],dword " "
add edi,4
mov ax,[Qgen_counter]
stdcall HexToDec
PRINT_CRLF
PRINT_CRLF
; p0 gen counter
mov [edi],dword "p0_g"
add edi,4
mov [edi],dword "en_c"
add edi,4
mov [edi],dword "ount"
add edi,4
mov [edi],dword ": "
add edi,4
mov ax,[P0gen_counter]
stdcall HexToDec
PRINT_CRLF
PRINT_CRLF
; p gen counter
mov [edi],dword "p_ge"
add edi,4
mov [edi],dword "n_co"
add edi,4
mov [edi],dword "unt:"
add edi,4
mov [edi],dword " "
add edi,4
mov ax,[Pgen_counter]
stdcall HexToDec
PRINT_CRLF
PRINT_CRLF
; first seed
mov [edi],dword "Firs"
add edi,4
mov [edi],dword "t Se"
add edi,4
mov [edi],dword "ed: "
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[First_Seed]
mov edx,32
stdcall PrintHexValue
; q seed
mov [edi],dword "q Se"
add edi,4
mov [edi],dword "ed: "
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Q_Seed]
mov edx,32
stdcall PrintHexValue
; p0 seed
mov [edi],dword "p0 S"
add edi,4
mov [edi],dword "eed:"
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[P0_Seed]
mov edx,32
stdcall PrintHexValue
; p seed
mov [edi],dword "p Se"
add edi,4
mov [edi],dword "ed: "
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[P_Seed]
mov edx,32
stdcall PrintHexValue
; prime q
mov [edi],dword "Prim"
add edi,4
mov [edi],dword "e q:"
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_Q]
mov edx,32
stdcall PrintHexValue
; prime p0
mov [edi],dword "Prim"
add edi,4
mov [edi],dword "e p0"
add edi,4
mov [edi],byte ':'
inc edi
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_P0]
mov edx,200
stdcall PrintHexValue
; prime p
mov [edi],dword "Prim"
add edi,4
mov [edi],dword "e p:"
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_P]
mov edx,400
stdcall PrintHexValue
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc PrintLastCandidate
; print current seed, last value of candidate prime, current t and last x
lea edi,[bfDisplay]
; current seed
mov [edi],dword "Curr"
add edi,4
mov [edi],dword "ent "
add edi,4
mov [edi],dword "Seed"
add edi,4
mov [edi],byte ':'
inc edi
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_Seed]
mov edx,32
stdcall PrintHexValue
; candidate prime
mov [edi],dword "Cand"
add edi,4
mov [edi],dword "idat"
add edi,4
mov [edi],dword "e Pr"
add edi,4
mov [edi],dword "ime:"
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Candidate]
mov edx,400
stdcall PrintHexValue
; first candidate prime
mov [edi],dword "Firs"
add edi,4
mov [edi],dword "t Ca"
add edi,4
mov [edi],dword "ndid"
add edi,4
mov [edi],dword "ate:"
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[First_Candidate]
mov edx,400
stdcall PrintHexValue
; last c0
mov [edi],dword "Last"
add edi,4
mov [edi],dword " c0:"
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Last_c0]
mov edx,400
stdcall PrintHexValue
; last x
mov [edi],dword "Last"
add edi,4
mov [edi],dword " x: "
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Last_x]
mov edx,400
stdcall PrintHexValue
; current t
mov [edi],dword "Curr"
add edi,4
mov [edi],dword "ent "
add edi,4
mov [edi],dword "t: "
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Current_t]
mov edx,400
stdcall PrintHexValue
; current z
mov [edi],dword "Curr"
add edi,4
mov [edi],dword "ent "
add edi,4
mov [edi],dword "z: "
add edi,4
PRINT_CRLF
PRINT_CRLF
lea esi,[Current_z]
mov edx,400
stdcall PrintHexValue
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc Print_q_Found
; the prime q has been found
lea edi,[bfDisplay]
lea esi,[szQFoundMsg]
stdcall AddStringToEDI
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_Q]
mov edx,32
stdcall PrintHexValue
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc Print_p0_Found
; the prime p0 has been found
lea edi,[bfDisplay]
lea esi,[szP0FoundMsg]
stdcall AddStringToEDI
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_P0]
mov edx,200
stdcall PrintHexValue
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc Print_p_Found
; the prime p has been found
lea edi,[bfDisplay]
lea esi,[szPFoundMsg]
stdcall AddStringToEDI
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_P]
mov edx,400
stdcall PrintHexValue
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc Print_pq_Found
; the primes p and q have been found
lea edi,[bfDisplay]
lea esi,[szPQFoundMsg]
stdcall AddStringToEDI
PRINT_CRLF
PRINT_CRLF
lea esi,[Prime_P]
mov edx,400
stdcall PrintHexValue
lea esi,[Prime_Q]
mov edx,32
stdcall PrintHexValue
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc PrintError uses esi edi
; print the error message to bfDisplay
lea edi,[bfDisplay]
; check the error code
cmp [nErrorCode],word 0
je .ERR_0
cmp [nErrorCode],word 1
je .ERR_1
cmp [nErrorCode],word 2
je .ERR_2
cmp [nErrorCode],word 3
je .ERR_3
cmp [nErrorCode],word 4
je .ERR_4
cmp [nErrorCode],word 5
je .ERR_5
cmp [nErrorCode],word 6
je .ERR_6
.ERR_0:
lea esi,[szErrMessage_0]
jmp .PRINT
.ERR_1:
lea esi,[szErrMessage_1]
jmp .PRINT
.ERR_2:
lea esi,[szErrMessage_2]
jmp .PRINT
.ERR_3:
lea esi,[szErrMessage_3]
jmp .PRINT
.ERR_4:
lea esi,[szErrMessage_4]
jmp .PRINT
.ERR_5:
lea esi,[szErrMessage_5]
jmp .PRINT
.ERR_6:
lea esi,[szErrMessage_6]
.PRINT:
mov dl,[esi]
cmp dl,0
je .DONE
mov [edi],dl
inc esi
inc edi
jmp .PRINT
.DONE:
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
; generate the prime q
; -------------------------------------------------------------------------------------
proc Generate_q
; generate the prime q
mov [nErrorCode],word 0
; get the first seed
stdcall GetFirstSeed
; initialise the counter
mov [Counter],word 0
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
cmp [DSA_N],word 256
je .256
jmp .ERR_1
.160:
; first generate the small prime c0
; pass length in AX
mov ax,22
stdcall ST_Random_Small_Prime
cmp al,0
je .ERR_1
; first random prime q
; pass length in AX
mov ax,42
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; next random prime q
; pass length in AX
mov ax,81
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; last random prime q
; pass length in AX
mov ax,160
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
jmp .SUCCESS
.224:
; first generate the small prime c0
mov ax,30
stdcall ST_Random_Small_Prime
cmp al,0
je .ERR_1
; first random prime q
; pass length in AX
mov ax,58
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; next random prime q
; pass length in AX
mov ax,113
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; last random prime q
; pass length in AX
mov ax,224
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
jmp .SUCCESS
.256:
; first generate the small prime c0
mov ax,18
stdcall ST_Random_Small_Prime
cmp al,0
je .ERR_1
; first random prime q
; pass length in AX
mov ax,34
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; next random prime q
; pass length in AX
mov ax,66
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; next random prime q
; pass length in AX
mov ax,129
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
stdcall Update_Last_c0
; last random prime q
; pass length in AX
mov ax,256
stdcall ST_Random_Prime_q
cmp al,0
je .ERR_2
jmp .SUCCESS
.ERR_1:
; failed to generate small prime
xor eax,eax
mov [nErrorCode],word 1
jmp .DONE
.ERR_2:
; failed to generate the prime q
xor eax,eax
mov [nErrorCode],word 2
jmp .DONE
.SUCCESS:
stdcall onPrimeFound_q
; AL = 1 for success
mov al,1
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc ST_Random_Prime_q uses esi edi
; generate the random prime q
; required length passed in AX
locals
length dw 0
endl
mov [length],ax
; clear the candidate prime
stdcall ClearCandidate
mov [Qgen_counter],word 0
; calculate x
; put nIterations into DL
; For the prime q, nIterations is always zero
; N = 160 / SHA-1: iterations = 0
; N = 224 / SHA-224: iterations = 0
; N = 256 / SHA-256: iterations = 0
xor edx,edx
mov dl,0
stdcall Calc_Random_x
xor edx,edx
mov dx,[length]
stdcall Fix_Length_x
stdcall Init_t
mov dx,[length]
stdcall FirstCandidate
.NEXT:
inc word [Counter]
inc word [Qgen_counter]
xor edx,edx
mov dl,0
stdcall Calc_a
stdcall Test_GCD
cmp al,0
je .NEXT_T
stdcall Test_Prime
cmp al,0
je .NEXT_T
stdcall Calc_z
; test q for primality
stdcall ST_Test_Primality
cmp al,1
je .SUCCESS
.NEXT_T:
; test: Qgen_counter greater than or equal to (4 x length)
mov dx,[length]
shl dx,2
cmp [Qgen_counter],dx
jge .FAILURE
; increment t
lea edi,[Current_t]
stdcall Increment
mov dx,[length]
; increment the candidate
stdcall NextCandidate
jmp .NEXT
.SUCCESS:
; AL = 1 for success
mov al,1
jmp .DONE
.FAILURE:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc onPrimeFound_q uses esi edi ecx
; set q, qseed and qgen_counter
lea esi,[Candidate]
lea edi,[Prime_Q]
xor ecx,ecx
.COPY:
; set the prime q
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .COPY
; set qseed
lea esi,[Prime_Seed]
lea edi,[Q_Seed]
xor ecx,ecx
.SEED:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .SEED
; qgen_counter
mov dx,[Counter]
mov [Qgen_counter],dx
; Prime_c
mov edx,[Prime_c0]
mov [Prime_c],edx
mov [Prime_c0],dword 0
ret
endp
; -------------------------------------------------------------------------------------
; generate the prime p0
; -------------------------------------------------------------------------------------
proc Generate_p0
; generate the prime p0
mov [nErrorCode],word 0
; initialise the counter
mov [Counter],word 0
; has the prime q been generated
stdcall IsPrimeQZero
cmp al,1
je .ERR_1
cmp [DSA_L],word 1024
je .1024
cmp [DSA_L],word 2048
je .1024
cmp [DSA_L],word 3072
je .3072
jmp .ERR_2
.1024:
; first generate the small prime c0
; pass length in AX
mov ax,18
stdcall ST_Random_Small_Prime
cmp al,0
je .ERR_2
; first random prime p0
; pass length in AX
mov ax,34
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,66
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,130
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,258
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
cmp [DSA_L],word 2048
je .2048
; last random prime p0
; pass length in AX
mov ax,513
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
jmp .SUCCESS
.2048:
; next random prime p0
; pass length in AX
mov ax,514
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; last random prime p0
; pass length in AX
mov ax,1025
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
jmp .SUCCESS
.3072:
; first generate the small prime c0
; pass length in AX
mov ax,26
stdcall ST_Random_Small_Prime
cmp al,0
je .ERR_2
; first random prime p0
; pass length in AX
mov ax,50
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,98
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,194
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,386
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; next random prime p0
; pass length in AX
mov ax,770
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
stdcall Update_Last_c0
; last random prime p0
; pass length in AX
mov ax,1537
stdcall ST_Random_Prime_p0
cmp al,0
je .ERR_3
jmp .SUCCESS
.ERR_1:
; prime q has not been generated
xor eax,eax
mov [nErrorCode],word 3
jmp .DONE
.ERR_2:
; failed to generate small prime
xor eax,eax
mov [nErrorCode],word 1
jmp .DONE
.ERR_3:
; failed to generate the prime p0
xor eax,eax
mov [nErrorCode],word 4
jmp .DONE
.SUCCESS:
stdcall onPrimeFound_p0
; AL = 1 for success
mov al,1
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc ST_Random_Prime_p0 uses esi edi
; generate the random prime p0
; required length passed in AX
locals
length dw 0
nIterations db 0
endl
; store the length
mov [length],ax
; get nIterations
stdcall Get_nIterations
; nIterations returned in AL
mov [nIterations],al
; clear the candidate prime
stdcall ClearCandidate
mov [P0gen_counter],word 0
; calculate x
; put nIterations into DL
xor edx,edx
mov dl,[nIterations]
stdcall Calc_Random_x
xor edx,edx
mov dx,[length]
stdcall Fix_Length_x
stdcall Init_t
mov dx,[length]
stdcall FirstCandidate
.NEXT:
inc word [Counter]
inc word [P0gen_counter]
mov dl,[nIterations]
stdcall Calc_a
stdcall Test_GCD
cmp al,0
je .NEXT_T
stdcall Test_Prime
cmp al,0
je .NEXT_T
stdcall Calc_z
; test p0 for primality
stdcall ST_Test_Primality
cmp al,1
je .SUCCESS
.NEXT_T:
; test: Qgen_counter greater than or equal to (4 x length)
mov dx,[length]
shl dx,2
cmp [P0gen_counter],dx
jge .FAILURE
; increment t
lea edi,[Current_t]
stdcall Increment
mov dx,[length]
; increment the candidate
stdcall NextCandidate
jmp .NEXT
.SUCCESS:
; AL = 1 for success
mov al,1
jmp .DONE
.FAILURE:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Get_nIterations uses ecx
; nIterations for the prime p0:
; N = 160 / SHA-1
; N = 224 / SHA-224
; N = 256 / SHA-256
; length passed in AX
locals
outlen dw 0
endl
xor ecx,ecx
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
cmp [DSA_N],word 256
je .256
.160:
inc cx
add [outlen],word 160
cmp ax,[outlen]
jle .DONE
jmp .160
.224:
inc cx
add [outlen],word 224
cmp ax,[outlen]
jle .DONE
jmp .224
.256:
inc cx
add [outlen],word 256
cmp ax,[outlen]
jle .DONE
jmp .256
.DONE:
; return nIterations in AL
xor eax,eax
dec cl
mov al,cl
ret
endp
; -------------------------------------------------------------------------------------
proc onPrimeFound_p0 uses esi edi ecx
; set p0, p0_seed and p0gen_counter
lea esi,[Candidate]
lea edi,[Prime_P0]
xor ecx,ecx
.COPY:
; set the prime p0
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,200
jl .COPY
; set p0_seed
lea esi,[Prime_Seed]
lea edi,[P0_Seed]
xor ecx,ecx
.SEED:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .SEED
; p0gen_counter
mov dx,[Counter]
mov [P0gen_counter],dx
ret
endp
; -------------------------------------------------------------------------------------
; computations for the primes q and p0
; -------------------------------------------------------------------------------------
proc Init_t uses esi edi
; calc: t = ceiling(x/2c0)
; divide Last_x by 2c0
lea esi,[Last_x]
; copy Last_x to the product buffer
stdcall CopyToProductBf
; set ShiftBf = 2c0
lea esi,[Last_c0]
stdcall CopyToShiftBf
; 2 x c0
lea edi,[ShiftBf]
stdcall ShiftLeft
; do the division: ProductBf by ShiftBf
stdcall Divide
; copy the quotient to the destination
lea edi,[Current_t]
stdcall QuotientToDest
; add 1 if there was a remainder
stdcall IsProductBfZero
cmp al,1
je .DONE
stdcall Increment
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_From_t uses esi edi
; calc: c = 2tc0 + 1
; set ShiftBf = 2c0
lea esi,[Last_c0]
stdcall CopyToShiftBf
; 2 x c0
lea edi,[ShiftBf]
stdcall ShiftLeft
lea esi,[Current_t]
; multiply ShiftBf by ESI
stdcall Multiply
; copy the result from ProductBf back to EDI
lea edi,[Candidate]
stdcall CopyFromProductBf
; add 1 to EDI
stdcall Increment
ret
endp
; -------------------------------------------------------------------------------------
proc FirstCandidate uses esi edi
; length passed in DX
locals
length dw 0
endl
mov [length],dx
; calc: c = 2tc0 + 1
stdcall Calc_From_t
; is (2tc0 + 1) greater than 2^length ?
; test if the bit at 2^length is set
mov dx,[length]
stdcall TestCandidateLength
cmp al,1
jne .DONE
; recalculate t
mov dx,[length]
stdcall Recalc_t
; recalculate the candidate
stdcall Calc_From_t
.DONE:
stdcall SaveFirstCandidate
ret
endp
; -------------------------------------------------------------------------------------
proc NextCandidate uses esi edi
; length passed in DX
locals
length dw 0
endl
mov [length],dx
; get the next Candidate
stdcall Calc_From_t
.TEST:
; is the Candidate greater than 2^length ?
; test if the bit at 2^length is set
mov dx,[length]
stdcall TestCandidateLength
cmp al,1
jne .DONE
; recalculate t
mov dx,[length]
stdcall Recalc_t
; recalculate the candidate
stdcall Calc_From_t
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Recalc_t uses esi edi ecx
; reset t
; t = ceiling(2^(length-1)/2c0)
; required length passed in DX
locals
length dw 0
endl
mov [length],dx
lea edi,[Current_t]
xor ecx,ecx
; zero t
stdcall ZeroHexBuffer
; set the bit at 2^(length-1)
; get the index of the byte containing the bit
; index of bit is length-1
dec dx
xor ecx,ecx
mov cx,dx
shr cx,3
; add to EDI
add edi,ecx
; get the index of the bit
and dx,7
mov cl,dl
; set the bit
mov al,1
shl al,cl
; or into EDI
or [edi],al
; copy the new t to ProductBf
lea esi,[Current_t]
stdcall CopyToProductBf
; divide 2c0 into ProductBf
; set ShiftBf = 2c0
lea esi,[Last_c0]
stdcall CopyToShiftBf
; 2 x c0
lea edi,[ShiftBf]
stdcall ShiftLeft
; do the division: ProductBf by ShiftBf
stdcall Divide
; copy the quotient to the destination
lea edi,[Current_t]
stdcall QuotientToDest
; add 1 if there was a remainder
stdcall IsProductBfZero
cmp al,1
je .DONE
stdcall Increment
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_a uses esi edi
; compute a (stored in Current_z)
; use the hash function to generate a random starter value for a
stdcall Calc_Random_a
; calc: a = 2 + (a mod (c-3))
lea esi,[Candidate]
stdcall CopyToShiftBf
; ShiftBf = (c-3)
lea edi,[ShiftBf]
stdcall Decrement
stdcall Decrement
stdcall Decrement
lea esi,[Current_z]
stdcall CopyToProductBf
; a mod (c-3)
stdcall Modulus
lea edi,[Current_z]
stdcall CopyFromProductBf
; add 2 to a
stdcall Increment
stdcall Increment
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_z uses esi edi
; calc: z = (a ^ 2t) mod c
; candidate to ModBf
lea esi,[Candidate]
stdcall CopyToModBf
; t to ExpBf
lea esi,[Current_t]
stdcall CopyToExpBf
; multiply Exp by 2
lea edi,[ExpBf]
stdcall HexShiftLeft
; z to BaseBf
lea esi,[Current_z]
stdcall CopyToBaseBf
; mod_exp
stdcall Mod_Exp
; copy result back to Current_z
lea edi,[Current_z]
stdcall CopyFromProductBf
ret
endp
; -------------------------------------------------------------------------------------
proc ST_Test_Primality uses esi edi
; Test if the candidate q or p0 is prime
; result returned in AL
; Test 1: GCD(z-1,Candidate) == 1
stdcall Calc_GCD
stdcall Check_GCD_Passed
cmp al,1
jne .DONE
; Test 2: (z ^ c0) mod c = 1
lea esi,[Current_z]
stdcall CopyToBaseBf
lea esi,[Last_c0]
stdcall CopyToExpBf
lea esi,[Candidate]
stdcall CopyToModBf
stdcall Mod_Exp
stdcall Check_MEXP_Passed
.DONE:
; if prime, AL = 1
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_GCD uses esi edi
; calc GCD of Candidate with (z-1)
lea esi,[Candidate]
stdcall CopyToProductBf
lea esi,[Current_z]
stdcall CopyToShiftBf
lea edi,[ShiftBf]
stdcall Decrement
.GCD:
stdcall Modulus
stdcall XchgProductBfShiftBf
stdcall IsShiftBfZero
cmp al,1
je .DONE
jmp .GCD
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Check_GCD_Passed uses esi ecx
; did the test prime pass the GCD test ?
lea esi,[ProductBf]
xor ecx,ecx
mov cx,DBL_HEX_LEN-1
.TEST:
cmp [esi+ecx],byte 0
jne .FAILED
dec cx
cmp cx,0
jg .TEST
; test [esi]
cmp [esi],byte 1
jne .FAILED
.PASSED:
mov al,1
jmp .DONE
.FAILED:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Check_MEXP_Passed uses esi ecx
; did the test prime pass the mod exp test ?
lea esi,[ProductBf]
xor ecx,ecx
mov cx,DBL_HEX_LEN-1
.TEST:
cmp [esi+ecx],byte 0
jne .FAILED
dec cx
cmp cx,0
jg .TEST
; test [esi]
cmp [esi],byte 1
jne .FAILED
.PASSED:
mov al,1
jmp .DONE
.FAILED:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Test_Prime uses esi edi
; does: a^(p-1) mod p = 1
lea esi,[Current_z]
stdcall CopyToBaseBf
lea esi,[Candidate]
stdcall CopyToExpBf
lea edi,[ExpBf]
stdcall Decrement
lea esi,[Candidate]
stdcall CopyToModBf
stdcall Mod_Exp
stdcall Check_MEXP_Passed
.DONE:
; if prime, AL = 1
ret
endp
; -------------------------------------------------------------------------------------
proc TestCandidateLength uses edi ecx
; test the bit length of the candidate
; required length passed in EDX
locals
length dw 0
count db 8
endl
mov [length],dx
lea edi,[Candidate]
xor ecx,ecx
mov cx,399
.FIND:
; find the first non zero byte
mov dl,[edi+ecx]
cmp dl,0
jne .COUNT
dec cx
cmp cx,0
jge .FIND
; the candidate is zero, if the loop exits here:
jmp .GT
.COUNT:
shl dl,1
jc .TEST
dec byte [count]
cmp [count],byte 0
jg .COUNT
.TEST:
; length of candidate = (8 x ECX) + count
shl ecx,3
xor edx,edx
mov dl,[count]
add ecx,edx
cmp cx,[length]
jg .GT
xor eax,eax
jmp .DONE
.GT:
; the length of the candidate is greater than the required length
mov al,1
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
; generate candidates for the prime p
; -------------------------------------------------------------------------------------
proc Random_Prime_P uses esi edi
; generate the random prime p
locals
nIterations db 0
endl
; clear the candidate prime
stdcall ClearCandidate
mov [Pgen_counter],word 0
; For the prime p:
; (1024,160): outlen = 160, iterations = 6
; (2048,224): outlen = 224, iterations = 9
; (2048,256): outlen = 256, iterations = 7
; (3072,256): outlen = 256, iterations = 11
; set nIterations:
mov [nIterations],byte 6
cmp [DSA_N],word 160
je .CALC_X
mov [nIterations],byte 9
cmp [DSA_N],word 224
je .CALC_X
mov [nIterations],byte 7
cmp [DSA_L],word 2048
je .CALC_X
mov [nIterations],byte 11
.CALC_X:
; calculate x
; put nIterations into DL
xor edx,edx
mov dl,[nIterations]
stdcall Calc_Random_x
xor edx,edx
mov dx,[DSA_L]
stdcall Fix_Length_x
stdcall Init_t_P
mov dx,[DSA_L]
stdcall FirstCandidate_P
.NEXT:
inc word [Counter]
inc word [Pgen_counter]
mov dl,[nIterations]
stdcall Calc_a
stdcall Test_GCD
cmp al,0
je .NEXT_T
stdcall Test_Prime
cmp al,0
je .NEXT_T
stdcall Calc_z_P
; test p for primality
stdcall Test_Primality_P
cmp al,1
je .SUCCESS
.NEXT_T:
; test: Qgen_counter greater than or equal to (4 x length)
mov dx,[DSA_L]
shl dx,2
cmp [Pgen_counter],dx
jge .FAILURE
; increment t
lea edi,[Current_t]
stdcall Increment
mov dx,[DSA_L]
; increment the candidate
stdcall NextCandidate_P
jmp .NEXT
.SUCCESS:
stdcall onPrimeFound_p
; AL = 1 for success
mov al,1
jmp .DONE
.FAILURE:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_2qp0 uses esi edi
; compute 2qp0
lea edi,[qp0x2]
stdcall ZeroHexBuffer
; put p0 into ShiftBf
stdcall CopyP0ToShiftBf
; multiply ShiftBf by 2
lea edi,[ShiftBf]
stdcall ShiftLeft
; multiply ESI by the ShiftBf
stdcall CopyQToTempBf
lea esi,[TempBf]
stdcall Multiply
; copy result from ProductBf to EDI
lea edi,[qp0x2]
stdcall CopyFromProductBf
ret
endp
; -------------------------------------------------------------------------------------
proc Init_t_P uses esi edi
; calc: t = ceiling(x/2qp0)
; calc 2qp0
stdcall Calc_2qp0
; divide Last_x by 2qp0
lea esi,[Last_x]
; copy Last_x to the product buffer
stdcall CopyToProductBf
; set divisor = 2qp0
lea esi,[qp0x2]
stdcall CopyToShiftBf
; do the division: ProductBf by ShiftBf
stdcall Divide
; copy the quotient to the destination
lea edi,[Current_t]
stdcall QuotientToDest
; add 1 if there was a remainder
stdcall IsProductBfZero
cmp al,1
je .DONE
stdcall Increment
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc FirstCandidate_P uses esi edi
; length passed in DX
locals
length dw 0
endl
mov [length],dx
; calc: c = 2tqp0 + 1
stdcall Calc_From_t_P
; is (2tqp0 + 1) greater than 2^length ?
; test if the bit at 2^length is set
mov dx,[length]
stdcall TestCandidateLength
cmp al,1
jne .DONE
; recalculate t
mov dx,[length]
stdcall Recalc_t_P
; recalculate the candidate
stdcall Calc_From_t_P
.DONE:
stdcall SaveFirstCandidate
ret
endp
; -------------------------------------------------------------------------------------
proc NextCandidate_P uses esi edi
; length passed in DX
locals
length dw 0
endl
mov [length],dx
; get the next Candidate
stdcall Calc_From_t_P
.TEST:
; is the Candidate greater than 2^length ?
; test if the bit at 2^length is set
mov dx,[length]
stdcall TestCandidateLength
cmp al,1
jne .DONE
; recalculate t
mov dx,[length]
stdcall Recalc_t_P
; recalculate the candidate
stdcall Calc_From_t_P
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_From_t_P uses esi edi
; calc: c = 2tqp0 + 1
lea esi,[qp0x2]
stdcall CopyToShiftBf
lea esi,[Current_t]
; multiply ShiftBf by ESI
stdcall Multiply
; copy the result from ProductBf back to EDI
lea edi,[Candidate]
stdcall CopyFromProductBf
; add 1 to EDI
stdcall Increment
ret
endp
; -------------------------------------------------------------------------------------
proc Recalc_t_P uses esi edi ecx
; reset t
; t = ceiling(2^(length-1)/2qp0)
; required length passed in DX
locals
length dw 0
endl
mov [length],dx
lea edi,[Current_t]
xor ecx,ecx
; zero t
stdcall ZeroHexBuffer
; set the bit at 2^(length-1)
; get the index of the byte containing the bit
; index of bit is length-1
dec dx
xor ecx,ecx
mov cx,dx
shr cx,3
; add to EDI
add edi,ecx
; get the index of the bit
and dx,7
mov cl,dl
; set the bit
mov al,1
shl al,cl
; or into EDI
or [edi],al
; copy the new t to ProductBf
lea esi,[Current_t]
stdcall CopyToProductBf
; divide 2c0 into ProductBf
lea esi,[qp0x2]
stdcall CopyToShiftBf
; do the division: ProductBf by ShiftBf
stdcall Divide
; copy the quotient to the destination
lea edi,[Current_t]
stdcall QuotientToDest
; add 1 if there was a remainder
stdcall IsProductBfZero
cmp al,1
je .DONE
stdcall Increment
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_z_P uses esi edi
; calc: z = (a ^ 2tq) mod p
; candidate to ModBf
lea esi,[Candidate]
stdcall CopyToModBf
; 2tq to ExpBf
stdcall Calc_2tq
; z to BaseBf
lea esi,[Current_z]
stdcall CopyToBaseBf
; mod_exp
stdcall Mod_Exp
; copy result back to Current_z
lea edi,[Current_z]
stdcall CopyFromProductBf
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_2tq uses esi edi
; put 2tq into ExpBf
stdcall CopyQToTempBf
lea esi,[TempBf]
stdcall CopyToShiftBf
; init ExpBf to 2t
lea esi,[Current_t]
stdcall CopyToExpBf
; multiply Exp by 2
lea edi,[ExpBf]
stdcall HexShiftLeft
; multiply ShiftBf by ExpBf
lea esi,[ExpBf]
stdcall Multiply
; copy result back to ExpBf
lea edi,[ExpBf]
stdcall CopyFromProductBf
ret
endp
; -------------------------------------------------------------------------------------
proc Test_Primality_P uses esi edi
; Test if the candidate p is prime
; result returned in AL
; Test 1: GCD(z-1,Candidate) == 1
stdcall Calc_GCD
stdcall Check_GCD_Passed
cmp al,1
jne .DONE
; Test 2: (z ^ p0) mod p = 1
lea esi,[Current_z]
stdcall CopyToBaseBf
; p0 to ExpBf
stdcall CopyP0ToExpBf
; candidate p to ModBf
lea esi,[Candidate]
stdcall CopyToModBf
stdcall Mod_Exp
stdcall Check_MEXP_Passed
.DONE:
; if prime, AL = 1
ret
endp
; -------------------------------------------------------------------------------------
proc Generate_p
; generate the prime p
mov [nErrorCode],word 0
; has the prime q been generated
stdcall IsPrimeQZero
cmp al,1
je .ERR_1
; has the prime q been generated
stdcall IsPrimeP0Zero
cmp al,1
je .ERR_2
stdcall Random_Prime_P
cmp al,0
je .ERR_3
; AL = 1 for success
mov al,1
jmp .DONE
.ERR_1:
; prime q has not been generated
xor eax,eax
mov [nErrorCode],word 3
jmp .DONE
.ERR_2:
; prime p0 has not been generated
xor eax,eax
mov [nErrorCode],word 5
jmp .DONE
.ERR_3:
; failed to generate the prime p
xor eax,eax
mov [nErrorCode],word 6
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc onPrimeFound_p uses esi edi ecx
; set p, p_seed and pgen_counter
lea esi,[Candidate]
lea edi,[Prime_P]
xor ecx,ecx
.COPY:
; set the prime p
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,400
jl .COPY
; set p_seed
lea esi,[Prime_Seed]
lea edi,[P_Seed]
xor ecx,ecx
.SEED:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .SEED
; pgen_counter
mov dx,[Counter]
mov [Pgen_counter],dx
ret
endp
; -------------------------------------------------------------------------------------
; Math functions
; -------------------------------------------------------------------------------------
proc Test_GCD uses esi edi ecx
; generate 50 random numbers and calc the GCD with the candidate prime
; candidate is eliminated as a prime if a GCD not equal to 1 is found
; result is returned in AL
; AL = 1 if all GCD's = 1
locals
count db 50
endl
; read the time stamp counter (into EDX:EAX)
rdtsc
; use RNG Linear Congruential Generator
; X(n+1) = (aX(n) + c) mod m
; a = 0x19660D, c = 0x3C6EF35F, m = 0x100000000
; X(0) = EAX - from rdtsc
.RAND:
mov edx,dword 0x19660D
; multiply EAX by EDX
mul edx
; result in EDX:EAX
add eax,0x3C6EF35F
.TEST:
; copy the test prime to the product buffer
lea esi,[Candidate]
stdcall CopyToProductBf
stdcall ZeroShiftBf
lea edi,[ShiftBf]
mov [edi],eax
stdcall Modulus
; put the 32 bit modulus into EDX
lea esi,[ProductBf]
mov edx,[esi]
; compute GCD of EAX and EDX
stdcall GCD_32
cmp edx,1
jne .NOT_COPRIME
dec byte [count]
cmp [count],byte 0
jg .RAND
; if the loop exits here, candidate passed all tests
mov al,1
jmp .DONE
.NOT_COPRIME:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc GCD_32 uses ebx ecx
; calc GCD(EAX,EDX)
; result returned in EDX
; store EAX in ECX
mov ecx,eax
.MOD:
mov ebx,edx
xor edx,edx
; divide EDX:EAX by EBX
div ebx
; remainder is in EDX
; if EDX is zero, EBX is the GCD
cmp edx,0
je .DONE
; the divisor EBX becomes the dividend EAX
mov eax,ebx
jmp .MOD
.DONE:
; put the GCD into EDX
mov edx,ebx
; restore EAX from ECX
mov eax,ecx
ret
endp
; -------------------------------------------------------------------------------------
proc CalcSum uses ecx
; Add two double sized hex numbers
; ESI and EDI are set outside of this procedure
mov cx,0
; save CF from iteration to iteration
; init CF = 0
clc
; push flags register to the stack
pushf
.SUM:
mov eax,dword [esi]
; get the flags register from the stack
popf
; [EDI] = [EDI] + [ESI] + CF
adc dword [edi],eax
; save the flags register to the stack, for the next iteration
pushf
; these affect the CF, which is why it has to be saved to the stack
add esi,4
add edi,4
add cx,4
; cmp also affects the CF
cmp cx,DBL_HEX_LEN
jl .SUM
; clean up the stack
popf
ret
endp
; -------------------------------------------------------------------------------------
proc CalcDiff uses ecx
; Calc difference between two double sized hex numbers
; diff = dest - src
; ESI and EDI are set outside of this procedure
mov cx,0
; compute diff as: diff = dest + ~src + 1
; the 1 is introduced by initialising CF to 1
; save CF from iteration to iteration
; init CF = 1
stc
; push flags register to the stack
pushf
.SUB:
mov eax,dword [esi]
; ~src here:
not eax
; get the flags register from the stack
popf
; [EDI] = [EDI] + ~[ESI] + CF
adc dword [edi],eax
; save the flags register to the stack, for the next iteration
pushf
; these affect the CF, which is why it has to be saved to the stack
add esi,4
add edi,4
add cx,4
; cmp also affects the CF
cmp cx,DBL_HEX_LEN
jl .SUB
; clean up the stack
popf
ret
endp
; -------------------------------------------------------------------------------------
proc HexShiftLeft uses ecx
; Shift dest number left by 1 bit
; EDI is set outside of this procedure
; start from the high order double word in the dest
add edi,HEX_LEN-4
mov cx,HEX_LEN-4
.SHIFT:
mov eax,dword [edi-4]
shld dword [edi],eax,1
sub edi,4
sub cx,4
cmp cx,0
jg .SHIFT
shl dword [edi],1
ret
endp
; -------------------------------------------------------------------------------------
proc ShiftLeft uses ecx
; Shift dest number left by 1 bit
; EDI is set outside of this procedure
; start from the high order double word in the dest
add edi,DBL_HEX_LEN-4
mov cx,DBL_HEX_LEN-4
.SHIFT:
mov eax,dword [edi-4]
shld dword [edi],eax,1
sub edi,4
sub cx,4
cmp cx,0
jg .SHIFT
shl dword [edi],1
ret
endp
; -------------------------------------------------------------------------------------
proc ShiftRight uses ecx
; Shift dest number right by 1 bit
; EDI is set outside of this procedure
mov cx,0
.SHIFT:
mov eax,dword [edi+4]
shrd dword [edi],eax,1
add edi,4
add cx,4
cmp cx,DBL_HEX_LEN-4
jl .SHIFT
shr dword [edi],1
ret
endp
; -------------------------------------------------------------------------------------
proc Multiply uses edi ecx
; calculate ProductBf = ESI * ShiftBf
; ESI is set outside of this procedure
locals
nBit db 0
endl
; zero ProductBf
stdcall ZeroProductBf
; ESI is a hex value of length HEX_LEN
; Algorithm:
; first find the byte in ESI containing the high order bit
; then starting from this byte, iterate through the bits in ESI
; start from the high order bit down to the low order bit
; for each iteration:
; (1) left shift ProductBf by 1 bit
; (2) test the bit
; (3) if the bit is set, add ShiftBf to ProductBf
mov cx,HEX_LEN
; start from end of ESI (the highest byte)
add esi,HEX_LEN-1
.FIND_HOB:
cmp byte [esi],0
jne .FOUND
dec esi
dec cx
cmp cx,0
je .QUIT
jmp .FIND_HOB
.FOUND:
; ESI now points to the byte that has the high order bit
; cx contains the byte number (index into A)
mov [nBit],byte 7
; load the byte at address ESI into BL for testing
mov bl,byte [esi]
.FIND_BIT:
test bl,0x80
jnz .HO_BIT
shl bl,1
dec [nBit]
cmp [nBit],byte 0
jl .QUIT
jmp .FIND_BIT
.HO_BIT:
; the high order bit has been found
; initialise ProductBf
stdcall AddShiftBfToProductBf
.NEXT_BIT:
; get the next bit
shl bl,1
dec [nBit]
cmp [nBit],byte 0
jl .NEXT_BYTE
jmp .SHIFT
.NEXT_BYTE:
; get the next byte
dec esi
dec cx
; no more bytes when cx = 0
cmp cx,0
jle .QUIT
mov [nBit],byte 7
mov bl,byte [esi]
.SHIFT:
; shift ProductBf 1 bit to the left
lea edi,[ProductBf]
stdcall ShiftLeft
; test the current bit to see if an addition is required
test bl,0x80
jz .NEXT_BIT
.ADD:
; add to ProductBf
stdcall AddShiftBfToProductBf
jmp .NEXT_BIT
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc AddShiftBfToProductBf uses esi edi
; add ShiftBf to ProductBf
lea esi,[ShiftBf]
lea edi,[ProductBf]
stdcall CalcSum
ret
endp
; -------------------------------------------------------------------------------------
proc Divide uses edi esi eax ecx
; divide ProductBf by ShiftBf
; ProductBf is of length DBL_HEX_LEN
; ShiftBf is of length DBL_HEX_LEN
; length of value in ShiftBf is up to HEX_LEN
; the remainder is left in ProductBf
; length of remainder is less than or equal to HEX_LEN
; result is in QuotientBf
stdcall ZeroQuotientBf
; if ShiftBf is zero, do nothing
stdcall IsShiftBfZero
cmp al,1
je .QUIT
; if ProductBf is less than ShiftBf, do nothing
stdcall IsProductBfLessThanShiftBf
cmp al,1
je .QUIT
; left shift ShiftBf to align the high order bits with ProductBf
locals
hob_PBf dw 0
hob_SBf dw 0
shift dw 0
endl
; find the high order bit in ProductBf
lea eax,[ProductBf]
stdcall FindHighOrderBit
; check if the high order bit was found
cmp eax,0xffffffff
je .QUIT
mov word [hob_PBf],ax
; find the high order bit in ShiftBf
lea eax,[ShiftBf]
stdcall FindHighOrderBit
; check if the high order bit was found
cmp eax,0xffffffff
je .QUIT
mov word [hob_SBf],ax
; compute how much to shift ShiftBf by
mov ax,[hob_PBf]
sub ax,[hob_SBf]
mov word [shift],ax
; do the shift
lea eax,[ShiftBf]
xor edx,edx
mov dx,word [shift]
stdcall BigLeftShift
; the high order bits of ProductBf and ShiftBf are now aligned
; Algorithm:
; for (shift + 1) bits in ProductBf starting from the high order bit:
; (1) determine if ProductBf is less than ShiftBf
; (2) if false, subtract ShiftBf from ProductBf
; (3) right shift ShiftBf by 1 bit
; (4) repeat from (1)
mov cx,word [shift]
.DIVIDE:
lea eax,[ProductBf]
lea edx,[ShiftBf]
stdcall IsLessThan
test al,1
jnz .SHIFT
lea edi,[ProductBf]
lea esi,[ShiftBf]
stdcall CalcDiff
mov dx,cx
stdcall AddBitToQuotient
.SHIFT:
; want to retain the original value of ShiftBf
; so when cx reaches 0, quit before the final shift
cmp cx,0
jle .QUIT
; right shift ShiftBf
lea edi,[ShiftBf]
stdcall ShiftRight
dec cx
jmp .DIVIDE
; the result is now in A
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc AddBitToQuotient uses edi eax ecx
; set the bit in QuotientBf
; bit index is passed in DX
lea edi,[QuotientBf]
xor ecx,ecx
mov cx,dx
; get the byte index
shr cx,3
; add to EDI
add edi,ecx
; get the bit index within the byte
and dx,7
mov cl,dl
mov al,1
shl al,cl
; set the bit in EDI
or [edi],al
ret
endp
; -------------------------------------------------------------------------------------
proc QuotientToDest uses esi ecx
; copy the quotient to EDI
; EDI is set outside of this procedure
lea esi,[QuotientBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc Modulus uses edi esi eax ecx
; calculate ProductBf mod ShiftBf
; ProductBf is of length DBL_HEX_LEN
; ShiftBf is of length DBL_HEX_LEN
; length of value in ShiftBf is up to HEX_LEN
; the remainder is left in ProductBf
; length of remainder is less than or equal to HEX_LEN
; if ShiftBf is zero, do nothing
stdcall IsShiftBfZero
cmp al,1
je .QUIT
; if ProductBf is less than ShiftBf, do nothing
stdcall IsProductBfLessThanShiftBf
cmp al,1
je .QUIT
; left shift ShiftBf to align the high order bits with ProductBf
locals
hob_PBf dw 0
hob_SBf dw 0
shift dw 0
endl
; find the high order bit in ProductBf
lea eax,[ProductBf]
stdcall FindHighOrderBit
; check if the high order bit was found
cmp eax,0xffffffff
je .QUIT
mov word [hob_PBf],ax
; find the high order bit in ShiftBf
lea eax,[ShiftBf]
stdcall FindHighOrderBit
; check if the high order bit was found
cmp eax,0xffffffff
je .QUIT
mov word [hob_SBf],ax
; compute how much to shift ShiftBf by
mov ax,[hob_PBf]
sub ax,[hob_SBf]
mov word [shift],ax
; do the shift
lea eax,[ShiftBf]
xor edx,edx
mov dx,word [shift]
stdcall BigLeftShift
; the high order bits of ProductBf and ShiftBf are now aligned
; Algorithm:
; for (shift + 1) bits in ProductBf starting from the high order bit:
; (1) determine if ProductBf is less than ShiftBf
; (2) if false, subtract ShiftBf from ProductBf
; (3) right shift ShiftBf by 1 bit
; (4) repeat from (1)
mov cx,word [shift]
.CALC_MOD:
lea eax,[ProductBf]
lea edx,[ShiftBf]
stdcall IsLessThan
test al,1
jnz .SHIFT
lea edi,[ProductBf]
lea esi,[ShiftBf]
stdcall CalcDiff
.SHIFT:
; want to retain the original value of ShiftBf
; so when cx reaches 0, quit before the final shift
cmp cx,0
jle .QUIT
; right shift ShiftBf
lea edi,[ShiftBf]
stdcall ShiftRight
dec cx
jmp .CALC_MOD
; the result is now in A
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc BigLeftShift uses esi edi ecx
; left shift a double hex value by more than 1 bit
; address is passed in EAX
; size of shift passed in EDX
mov edi,eax
mov esi,eax
locals
nBytes dw 0
nBits db 0
addr dd ?
endl
; save the address for later
mov dword [addr],eax
; size of shift = 8 * nBytes + nBits
; get nBits
mov al,dl
and al,7
mov byte [nBits],al
; get nBytes
shr dx,3
mov word [nBytes],dx
cmp word [nBytes],0
je .BITS
cmp word [nBytes],DBL_HEX_LEN
jge .ZERO_HEX
; copy up the bytes in the hex value by nBytes
add edi,DBL_HEX_LEN-1
add esi,DBL_HEX_LEN-1
sub si,word [nBytes]
mov cx,DBL_HEX_LEN
sub cx,word [nBytes]
; copy up (DBL_HEX_LEN - nBytes) bytes
.COPY_UP:
mov al,[esi]
mov [edi],al
dec esi
dec edi
dec cx
cmp cx,0
jg .COPY_UP
mov cx,word [nBytes]
; fill the rest of the hex array with zero bytes
.FILL_0:
mov [edi],byte 0
dec edi
dec cx
cmp cx,0
jg .FILL_0
; all done if nBits is zero
cmp byte [nBits],0
je .DONE
.BITS:
; set edi back to the high order dword in the hex value
mov edi,dword [addr]
add edi,DBL_HEX_LEN-4
mov cx,DBL_HEX_LEN-4
.SHIFT_BITS:
mov eax,[edi-4]
push cx
mov cl,byte [nBits]
shld dword [edi],eax,cl
pop cx
sub edi,4
sub cx,4
cmp cx,0
jg .SHIFT_BITS
mov cl,byte [nBits]
shl dword [edi],cl
jmp .DONE
.ZERO_HEX:
; shift is greater than the size of the hex value, just set to zero
; zero EDI
stdcall ZeroDoubleHexBuffer
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc FindHighOrderBit uses esi ecx
; scan a double hex length value for the high order bit
; return an index number giving the position of the high order bit
; address passed in EAX
; index returned in EAX
mov esi,eax
; start from the high order byte
add esi,DBL_HEX_LEN-1
mov cx,DBL_HEX_LEN
mov eax,DBL_HEX_LEN-1
; scan byte by byte for the first non-zero byte
.SCAN:
cmp byte [esi],0
jne .FOUND
dec cx
cmp cx,0
; not found if cx = 0, so quit
jle .NOT_FOUND
dec esi
dec eax
jmp .SCAN
.FOUND:
; multiply EAX by 8
shl eax,3
mov ebx,7
mov dl,byte [esi]
.FIND_BIT:
test dl,0x80
jnz .FINISH
shl dl,1
dec bl
cmp bl,0
jl .NOT_FOUND
jmp .FIND_BIT
.FINISH:
; add the bit position to get the final index value
add eax,ebx
jmp .DONE
.NOT_FOUND:
mov eax,0xffffffff
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc IsLessThan uses esi edi ecx
; is A less than B ?
; A and B are treated as unsigned values
; address of A passed in EAX
; address of B passed in EDX
mov edi,eax
mov esi,edx
; start from the high order bytes
add esi,DBL_HEX_LEN-4
add edi,DBL_HEX_LEN-4
mov cx,0
; result is returned in AL
xor al,al
.CHECK_LT:
mov edx,dword [edi]
cmp edx,dword [esi]
jb .LESS_THAN
jnbe .QUIT
add cx,4
cmp cx,DBL_HEX_LEN
jge .QUIT
sub esi,4
sub edi,4
jmp .CHECK_LT
; AL = true if less than
.LESS_THAN:
mov al,1
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc Mod_Exp uses esi edi
; compute Mod_Exp = pow(A,B) mod C
; A is in BaseBf
; B is in ExpBf
; C is in ModBf
; result in ProductBf
locals
nBit db 0
index dw 0
bits db 0
endl
stdcall ZeroProductBf
; if C is zero, do nothing
stdcall IsModBfZero
cmp al,1
je .QUIT
; init ProductBf to 1
lea edi,[ProductBf]
mov [edi],byte 1
; if B is zero, do nothing
stdcall IsExpBfZero
cmp al,1
je .QUIT
; ProductBf is now 1
.START:
; find the first non zero byte in ExpBf
lea esi,[ExpBf]
xor ecx,ecx
mov cx,HEX_LEN-1
.FIND:
cmp [esi+ecx],byte 0
jne .FOUND
dec cx
cmp cx,0
jge .FIND
; if the loop exits here, ExpBf is zero
jmp .QUIT
.FOUND:
; save the index
mov [index],cx
; save the byte
mov al,byte [esi+ecx]
mov [bits],al
; set the bit index
mov [nBit],byte 8
; start processing
.SQUARE:
; always square, whether the bit is 0 or 1
; square the value in ProductBf
stdcall CopyProductBfToShiftBf
stdcall CopyProductBfToTempBf
stdcall ZeroProductBf
lea esi,[TempBf]
stdcall Multiply
stdcall CopyModBfToShiftBf
stdcall Modulus
.TEST:
; only multiply if the bit is 1
; decrement the bit index
dec [nBit]
; test the bit in [bits]
shl byte [bits],1
jnc .NEXT_BIT
.MULTIPLY:
; multiply ProductBf by BaseBf
stdcall CopyProductBfToShiftBf
stdcall ZeroProductBf
lea esi,[BaseBf]
stdcall Multiply
stdcall CopyModBfToShiftBf
stdcall Modulus
.NEXT_BIT:
; if nBit = 0, will need to get the next byte
cmp [nBit],byte 0
jg .SQUARE
.NEXT_BYTE:
; get the next byte
; if index = 0, there is no next byte, so quit
cmp [index],word 0
je .QUIT
dec word [index]
mov [nBit],byte 8
; make sure ESI points to ExpBf
lea esi,[ExpBf]
xor ecx,ecx
mov cx,[index]
mov al,byte [esi+ecx]
mov [bits],al
jmp .SQUARE
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc IsHexZero uses ecx
; is a hex number of length HEX_LEN equal to zero ?
; EDI is set outside of this procedure
; EDI is not modifed by this procedure
xor ecx,ecx
.TEST:
cmp [edi+ecx],byte 0
jne .NON_ZERO
inc cx
cmp cx,HEX_LEN
jl .TEST
; if the loop exits here, the value is zero
mov al,1
jmp .DONE
.NON_ZERO:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc IsDblHexZero uses ecx
; is a double hex number of length DBL_HEX_LEN equal to zero ?
; EDI is set outside of this procedure
; EDI is not modifed by this procedure
xor ecx,ecx
.TEST:
cmp [edi+ecx],byte 0
jne .NON_ZERO
inc cx
cmp cx,DBL_HEX_LEN
jl .TEST
; if the loop exits here, the value is zero
mov al,1
jmp .DONE
.NON_ZERO:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Increment uses ecx
; increment the value in EDI
; EDI is set outside of this procedure
add [edi],byte 1
jnc .DONE
xor ecx,ecx
mov cx,1
.ADD_C:
add [edi+ecx],byte 1
jnc .DONE
inc cx
cmp cx,HEX_LEN
jl .ADD_C
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Decrement uses ecx
; decrement the value in EDI
; EDI is set outside of this procedure
sub [edi],byte 1
jnc .DONE
xor ecx,ecx
mov cx,1
.SUB_B:
sub [edi+ecx],byte 1
jnc .DONE
inc cx
cmp cx,HEX_LEN
jl .SUB_B
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
; use the Hash functions to create a random integer of the required length
; -------------------------------------------------------------------------------------
proc Calc_Random_x uses edi
; use the hash function to generate the random number x
; number of iterations passed in DL
locals
nIterations db 0
endl
mov [nIterations],dl
inc byte [nIterations]
; clear the temp buffer
stdcall ClearTempBuffer
xor eax,eax
cmp [DSA_N],160
je .SHA_1
cmp [DSA_N],224
je .SHA_224
cmp [DSA_N],256
je .SHA_256
jmp .DONE
.SHA_1:
; x = x + SHL(Hash(Prime_Seed),outlen x iteration)
stdcall HashSeed_SHA_1
stdcall Add_Hash_1
stdcall IncrementSeed
add eax,20
dec byte [nIterations]
cmp [nIterations],byte 0
jg .SHA_1
jmp .DONE
.SHA_224:
; x = x + SHL(Hash(Prime_Seed),outlen x iteration)
stdcall HashSeed_SHA_224
stdcall Add_Hash_224
stdcall IncrementSeed
add eax,28
dec byte [nIterations]
cmp [nIterations],byte 0
jg .SHA_224
jmp .DONE
.SHA_256:
; x = x + SHL(Hash(Prime_Seed),outlen x iteration)
stdcall HashSeed_SHA_256
stdcall Add_Hash_256
stdcall IncrementSeed
add eax,32
dec byte [nIterations]
cmp [nIterations],byte 0
jg .SHA_256
.DONE:
; copy from the result from TempBf to Last_x
lea edi,[Last_x]
stdcall CopyFromTempBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc Fix_Length_x uses edi ecx
; make sure Last_x has the length as given in EDX (in bits)
; i.e. x = 2^(length-1) + (x mod 2^(length-1))
; truncate and then set the bit at 2^(length-1)
lea edi,[Last_x]
; calc the byte index of the high order bit
mov ecx,edx
dec ecx
shr ecx,3
; zero all bytes above the byte containing the HOB
inc ecx
.ZERO:
mov [edi+ecx],byte 0
inc ecx
cmp ecx,400
jl .ZERO
.SET:
; get the bit index
mov ecx,edx
dec ecx
and ecx,7
; generate a bit mask
inc ecx
mov ax,1
shl ax,cl
dec ax
; and the bit mask into the byte in EDI
mov ecx,edx
dec ecx
shr ecx,3
and [edi+ecx],al
; make sure the HOB is set
inc ax
shr ax,1
or [edi+ecx],al
ret
endp
; -------------------------------------------------------------------------------------
proc Calc_Random_a uses esi edi ecx
; use the hash function to generate the random number a
; number of iterations passed in DL
locals
nIterations db 0
endl
mov [nIterations],dl
inc byte [nIterations]
; clear the temp buffer
stdcall ClearTempBuffer
xor eax,eax
cmp [DSA_N],160
je .SHA_1
cmp [DSA_N],224
je .SHA_224
cmp [DSA_N],256
je .SHA_256
jmp .NEXT
.SHA_1:
; a = a + SHL(Hash(Prime_Seed),outlen x iteration)
stdcall HashSeed_SHA_1
stdcall Add_Hash_1
stdcall IncrementSeed
add eax,20
dec byte [nIterations]
cmp [nIterations],byte 0
jg .SHA_1
jmp .NEXT
.SHA_224:
; a = a + SHL(Hash(Prime_Seed),outlen x iteration)
stdcall HashSeed_SHA_224
stdcall Add_Hash_224
stdcall IncrementSeed
add eax,28
dec byte [nIterations]
cmp [nIterations],byte 0
jg .SHA_224
jmp .NEXT
.SHA_256:
; a = a + SHL(Hash(Prime_Seed),outlen x iteration)
stdcall HashSeed_SHA_256
stdcall Add_Hash_256
stdcall IncrementSeed
add eax,32
dec byte [nIterations]
cmp [nIterations],byte 0
jg .SHA_256
.NEXT:
; copy from the result from TempBf to Current_z
lea edi,[Current_z]
stdcall CopyFromTempBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc Add_Hash_1 uses esi edi ecx edx
; offset in EAX
lea esi,[HashInteger]
lea edi,[TempBf]
xor ecx,ecx
add edi,eax
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,20
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc Add_Hash_224 uses esi edi ecx edx
; offset in EAX
lea esi,[HashInteger]
lea edi,[TempBf]
xor ecx,ecx
add edi,eax
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,28
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc Add_Hash_256 uses esi edi ecx edx
; offset in EAX
lea esi,[HashInteger]
lea edi,[TempBf]
xor ecx,ecx
add edi,eax
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
; Input/Output functions
; -------------------------------------------------------------------------------------
proc CountDigits uses esi ecx
; count the number of hex digits in the bfDisplay string
mov ax,0
xor ecx,ecx
lea esi,[bfDisplay]
.COUNT:
mov dl,[esi]
cmp dl,0
je .DONE
inc cx
inc esi
jmp .COUNT
.DONE:
; return the digit count in AX
mov ax,cx
ret
endp
; -------------------------------------------------------------------------------------
proc StrToHexStr uses esi edi
; filter out any non hex digit characters from the bfDisplay string
lea esi,[bfDisplay]
lea edi,[bfDisplay]
.FILTER:
mov al,[esi]
cmp al,0
je .DONE
cmp al,48
jl .NOT_HEX
cmp al,57
jle .COPY
cmp al,65
jl .NOT_HEX
cmp al,70
jle .COPY
cmp al,97
jl .NOT_HEX
cmp al,102
jg .NOT_HEX
.COPY:
mov [edi],al
inc edi
.NOT_HEX:
inc esi
jmp .FILTER
.DONE:
; null terminate the new string
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc HexDigitToValue
; convert a hex digit to a 4 bit value
; input in AL - output in AL
; is AL in the range: 48 - 57 (0 - 9) ?
cmp al,48
jl .NOT_HEX
cmp al,57
jg .A_Z
sub al,48
jmp .DONE
.A_Z:
; is AL in the range: 65 - 70 (A - B) ?
cmp al,65
jl .NOT_HEX
cmp al,70
jg .a_z
sub al,55
jmp .DONE
.a_z:
; is AL in the range: 97 - 102 (a - b) ?
cmp al,97
jl .NOT_HEX
cmp al,102
jg .NOT_HEX
sub al,87
jmp .DONE
.NOT_HEX:
; set EAX to 0xffff if input is not a valid hex digit
mov eax,0xffff
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc ByteToDigits
; convert 1 byte to 2 hex digits
; input in AL - output in AX
; copy AL to AH
mov ah,al
; AH: get the upper 4 bits of the byte
shr ah,4
; nibble to hex digit
add ah,48
cmp ah,57
jle .NEXT
add ah,7
.NEXT:
; AL: get the lower 4 bits of the byte
and al,0xf
; nibble to hex digit
add al,48
cmp al,57
jle .DONE
add al,7
.DONE:
; output is in AX
ret
endp
; -------------------------------------------------------------------------------------
proc PrintHexValue uses ecx
; ESI and EDI set outside of this procedure
; pass number of bytes to print in EDX
locals
count db 0
endl
mov cx,dx
sub cx,4
.FIND:
; find first non zero dword
mov eax,[esi+ecx]
cmp eax,dword 0
jne .PRINT
sub cx,4
cmp cx,0
jg .FIND
.PRINT:
mov eax,[esi+ecx]
; dword to 8 digits
stdcall DWordToStr
jcxz .DONE
sub cx,4
inc [count]
; add a CRLF to the output string after every 8 dwords
cmp [count],byte 8
je .ADD_CRLF
jmp .PRINT
.ADD_CRLF:
mov [count],byte 0
PRINT_CRLF
jmp .PRINT
.DONE:
PRINT_CRLF
PRINT_CRLF
ret
endp
; -------------------------------------------------------------------------------------
proc WordToStr uses edx
; print a word (2 bytes) to a string
; word passed in AX
; EDI set outside of this function
mov dx,ax
mov al,ah
stdcall ByteToDigits
mov [edi],ah
inc edi
mov [edi],al
inc edi
mov al,dl
stdcall ByteToDigits
mov [edi],ah
inc edi
mov [edi],al
inc edi
ret
endp
; -------------------------------------------------------------------------------------
proc DWordToStr
; print a dword (4 bytes) to a string
; word passed in EAX
; EDI set outside of this function
locals
tmp dw 0
endl
mov word [tmp],ax
shr eax,16
stdcall WordToStr
mov ax,word [tmp]
stdcall WordToStr
; add a space
mov [edi],byte 32
inc edi
ret
endp
; -------------------------------------------------------------------------------------
; seed functions
; -------------------------------------------------------------------------------------
proc ReadFirstSeed uses esi edi ecx
; read the 256 bit (32 byte) first seed from the bfDisplay string
; filter out any non hex digit chars from bfDisplay
stdcall StrToHexStr
; reset the first seed
stdcall ClearFirstSeed
lea esi,[bfDisplay]
; truncate bfDisplay so that it has no more than 64 hex digits
mov [esi+64],byte 0
lea edi,[First_Seed]
; count the digits in bfDisplay and save to AX
stdcall CountDigits
; check if the input buffer is empty
cmp ax,0
je .DONE
; calculate the offset in bytes from the start of EDI
; based on the number of digits in the input buffer (given by AX)
xor ecx,ecx
mov cx,ax
shr cx,1
test ax,1
jnz .ODD
.EVEN:
; the input buffer contains an even number of hex digits
; offset = (nDigits/2) - 1
dec cx
add edi,ecx
jmp .GET_DIGITS
.ODD:
; the input buffer contains an odd number of hex digits
; offset = nDigits/2
; convert the first digit
add edi,ecx
mov al,[esi]
stdcall HexDigitToValue
mov [edi],al
inc esi
dec edi
dec cx
cmp cx,0
jl .DONE
.GET_DIGITS:
; convert 2 hex digits to 1 byte
mov al,[esi]
stdcall HexDigitToValue
shl al,4
mov [edi],al
inc esi
mov al,[esi]
stdcall HexDigitToValue
or [edi],al
inc esi
dec cx
cmp cx,0
jl .DONE
dec edi
jmp .GET_DIGITS
.DONE:
; if N = 160 or N = 224, truncate the first seed
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
jmp .QUIT
.160:
lea edi,[First_Seed]
; truncate the first seed to 160 bits
mov [edi+20],dword 0
mov [edi+24],dword 0
mov [edi+28],dword 0
jmp .QUIT
.224:
lea edi,[First_Seed]
; truncate the first seed to 224 bits
mov [edi+28],dword 0
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc PrintFirstSeed uses esi edi ecx
; print the first seed to bfDisplay
lea esi,[First_Seed]
lea edi,[bfDisplay]
xor ecx,ecx
mov cx,16
cmp [DSA_N],word 160
je .PRINT
mov cx,24
cmp [DSA_N],word 224
je .PRINT
mov cx,28
.PRINT:
mov eax,[esi+ecx]
; dword to 8 digits
stdcall DWordToStr
jcxz .DONE
sub cx,4
jmp .PRINT
.DONE:
mov [edi],byte 0
ret
endp
; -------------------------------------------------------------------------------------
proc ClearFirstSeed uses edi ecx
; reset the first seed
lea edi,[First_Seed]
xor ecx,ecx
.CLEAR:
mov [edi+ecx],byte 0
inc cx
cmp cx,32
jl .CLEAR
ret
endp
; -------------------------------------------------------------------------------------
proc GenerateRandomFirstSeed uses edi ecx
; generate a random 256 bit (32 byte) first seed
stdcall ClearFirstSeed
; read the time stamp counter (into EDX:EAX)
rdtsc
; use RNG Linear Congruential Generator
; X(n+1) = (aX(n) + c) mod m
; a = 0x19660D, c = 0x3C6EF35F, m = 0x100000000
; X(0) = EAX - from rdtsc
lea edi,[First_Seed]
xor ecx,ecx
.RAND:
mov edx,dword 0x19660D
; multiply EAX by EDX
mul edx
; result in EDX:EAX
add eax,0x3C6EF35F
mov [edi+ecx],al
inc cx
cmp cx,32
jl .RAND
; if N = 160 or N = 224, truncate the first seed
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
jmp .DONE
.160:
lea edi,[First_Seed]
; truncate the first seed to 160 bits
mov [edi+20],dword 0
mov [edi+24],dword 0
mov [edi+28],dword 0
jmp .DONE
.224:
lea edi,[First_Seed]
; truncate the first seed to 224 bits
mov [edi+28],dword 0
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc GetFirstSeed uses esi edi ecx
; use the first seed to init the seed value
lea esi,[First_Seed]
lea edi,[Prime_Seed]
xor ecx,ecx
.TEST:
; is the first seed zero ?
cmp [esi+ecx],dword 0
jne .NEXT
add cx,4
cmp cx,32
jl .TEST
; the first seed is zero, generate a random value
stdcall GenerateRandomFirstSeed
.NEXT:
xor ecx,ecx
; init the seed value from the first seed
.COPY:
mov edx,[esi+ecx]
mov [edi+ecx],edx
add cx,4
cmp cx,32
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc IncrementSeed uses edi ecx
; increment the seed
lea edi,[Prime_Seed]
xor ecx,ecx
add [edi],byte 1
jnc .DONE
.ADD_C:
inc cx
cmp cx,32
jge .DONE
add [edi+ecx],byte 1
jc .ADD_C
.DONE:
; if N = 160 or N = 224, truncate the first seed
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
jmp .QUIT
.160:
lea edi,[First_Seed]
; truncate the first seed to 160 bits
mov [edi+20],dword 0
mov [edi+24],dword 0
mov [edi+28],dword 0
jmp .QUIT
.224:
lea edi,[First_Seed]
; truncate the first seed to 224 bits
mov [edi+28],dword 0
.QUIT:
ret
endp
; -------------------------------------------------------------------------------------
proc SeedToHashMessage uses esi edi eax ecx
; copy the 256 bit (32 byte) seed to the hash message block
; only one 512 bit message block is needed
; the SHA functions expects the message block to have the big endian byte order
; convert the seed to a bit string
stdcall SeedToBitString
; then copy to the hash message block
lea esi,[BitString]
lea edi,[MESSAGE]
xor ecx,ecx
.COPY:
; the first 32 bytes contain the seed (in big endian byte order)
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .COPY
; zero the padding bits
.ZERO:
mov [edi+ecx],byte 0
inc cx
cmp cx,64
jl .ZERO
; set the number of 512 bit blocks
mov [nBlocks512],dword 1
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
cmp [DSA_N],word 256
je .256
.160:
; set the bit length = 160
mov [BitLength],dword 160
; the first bit after the 20 seed bytes is set to 1
mov [edi+20],byte 0x80
jmp .BIT_LEN
.224:
; set the bit length = 224
mov [BitLength],dword 224
; the first bit after the 28 seed bytes is set to 1
mov [edi+28],byte 0x80
jmp .BIT_LEN
.256:
; set the bit length = 256
mov [BitLength],dword 256
; the first bit after the 32 seed bytes is set to 1
mov [edi+32],byte 0x80
.BIT_LEN:
; BitLength is a dword (32 bits)
; copy to the last 32 bits of the block
mov eax,[BitLength]
; big endian byte order
bswap eax
mov [edi+60],eax
ret
endp
; -------------------------------------------------------------------------------------
proc SeedToBitString uses esi edi ecx
; convert the seed number to a bit string
; the conversion is done by reversing the byte order
; the seed number is in little endian byte order
; the seed bit string is in big endian byte order
; the dwords within each are indexed from 0 to 7
; first the order of the dwords is reversed
; then the byte order within each dword is reversed, using the BSWAP instruction
lea esi,[Prime_Seed]
lea edi,[BitString]
add edi,28
mov cx,0
.CONVERT:
mov edx,[esi]
bswap edx
mov [edi],edx
add esi,4
sub edi,4
inc cx
cmp cx,8
jl .CONVERT
; if N = 160 or N = 224 the bits need to be shifted down by 12 bytes or 4 bytes
cmp [DSA_N],word 160
je .160
cmp [DSA_N],word 224
je .224
jmp .DONE
.160:
lea esi,[BitString]
lea edi,[BitString]
xor ecx,ecx
.COPY_3:
; copy down the dwords
mov edx,[esi+12]
mov [edi],edx
mov [esi+12],dword 0
add esi,4
add edi,4
inc cx
cmp cx,5
jl .COPY_3
jmp .DONE
.224:
lea esi,[BitString]
lea edi,[BitString]
xor ecx,ecx
.COPY_1:
; copy down the dwords
mov edx,[esi+4]
mov [edi],edx
mov [esi+4],dword 0
add esi,4
add edi,4
inc cx
cmp cx,7
jl .COPY_1
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc SHA_1_ToInteger uses esi edi ecx
; convert the hash result H_0_1 to an integer value
; by reversing the order of the dwords within the hash result
; within each dword the byte order is already little endian, no need to call BSWAP
; H_0_1 = 5 x 4 byte words
lea esi,[H_0_1]
add esi,16
lea edi,[HashInteger]
mov cx,0
.CONVERT:
mov edx,[esi]
mov [edi],edx
sub esi,4
add edi,4
inc cx
cmp cx,5
jl .CONVERT
; zero the rest of the HashInteger value
.ZERO:
mov [edi],dword 0
add edi,4
inc cx
cmp cx,8
jl .ZERO
ret
endp
; -------------------------------------------------------------------------------------
proc SHA_224_ToInteger uses esi edi ecx
; convert the hash result H_0_256 to an integer value
; by reversing the order of the dwords within the hash result
; within each dword the byte order is already little endian, no need to call BSWAP
; for SHA-224, H_0_256 = 7 x 4 byte words
lea esi,[H_0_256]
add esi,24
lea edi,[HashInteger]
mov cx,0
.CONVERT:
mov edx,[esi]
mov [edi],edx
sub esi,4
add edi,4
inc cx
cmp cx,7
jl .CONVERT
; zero the last dword in the HashInteger value
mov [edi],dword 0
ret
endp
; -------------------------------------------------------------------------------------
proc SHA_256_ToInteger uses esi edi ecx
; convert the hash result H_0_256 to an integer value
; by reversing the order of the dwords within the hash result
; within each dword the byte order is already little endian, no need to call BSWAP
; H_0_256 = 8 x 4 byte words
lea esi,[H_0_256]
add esi,28
lea edi,[HashInteger]
mov cx,0
.CONVERT:
mov edx,[esi]
mov [edi],edx
sub esi,4
add edi,4
inc cx
cmp cx,8
jl .CONVERT
ret
endp
; -------------------------------------------------------------------------------------
proc HashSeed_SHA_1
stdcall SeedToHashMessage
stdcall Compute_SHA_1
stdcall SHA_1_ToInteger
ret
endp
; -------------------------------------------------------------------------------------
proc HashSeed_SHA_224
stdcall SeedToHashMessage
stdcall Compute_SHA_224
stdcall SHA_224_ToInteger
ret
endp
; -------------------------------------------------------------------------------------
proc HashSeed_SHA_256
stdcall SeedToHashMessage
stdcall Compute_SHA_256
stdcall SHA_256_ToInteger
ret
endp
; -------------------------------------------------------------------------------------
; SHA-1, SHA-224, SHA-256 functions
; -------------------------------------------------------------------------------------
proc Init_H_0_SHA_1 uses edi
lea edi,[H_0_1]
mov [edi],dword 0x67452301
mov [edi+4],dword 0xefcdab89
mov [edi+8],dword 0x98badcfe
mov [edi+12],dword 0x10325476
mov [edi+16],dword 0xc3d2e1f0
ret
endp
; -------------------------------------------------------------------------------------
proc Init_H_0_SHA_224 uses edi
lea edi,[H_0_256]
mov [edi],dword 0xc1059ed8
mov [edi+4],dword 0x367cd507
mov [edi+8],dword 0x3070dd17
mov [edi+12],dword 0xf70e5939
mov [edi+16],dword 0xffc00b31
mov [edi+20],dword 0x68581511
mov [edi+24],dword 0x64f98fa7
mov [edi+28],dword 0xbefa4fa4
ret
endp
; -------------------------------------------------------------------------------------
proc Init_H_0_SHA_256 uses edi
lea edi,[H_0_256]
mov [edi],dword 0x6a09e667
mov [edi+4],dword 0xbb67ae85
mov [edi+8],dword 0x3c6ef372
mov [edi+12],dword 0xa54ff53a
mov [edi+16],dword 0x510e527f
mov [edi+20],dword 0x9b05688c
mov [edi+24],dword 0x1f83d9ab
mov [edi+28],dword 0x5be0cd19
ret
endp
; -------------------------------------------------------------------------------------
proc Compute_SHA_1 uses esi edi eax ecx
; process the single 512 bit (64 byte) message block
; this function expects the message block to have the big endian byte ordering
stdcall Init_H_0_SHA_1
mov ecx,[nBlocks512]
lea esi,[MESSAGE]
.HASH_BLOCK:
lea edi,[Message_Schedule]
mov edx,64
.INIT_SCHED:
; copy the 512 bit block to the first 512 bits of the message schedule
mov eax,[esi]
; big endian to little endian
bswap eax
mov [edi],eax
add esi,4
add edi,4
sub dx,4
cmp dx,0
jg .INIT_SCHED
; iterate the hash value
stdcall SHA_1_Iterate
dec cx
jcxz .DONE
jmp .HASH_BLOCK
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Compute_SHA_224 uses esi edi eax ecx
; process the single 512 bit (64 byte) message block
; this function expects the message block to have the big endian byte ordering
stdcall Init_H_0_SHA_224
mov ecx,[nBlocks512]
lea esi,[MESSAGE]
.HASH_BLOCK:
lea edi,[Message_Schedule]
mov dx,64
.INIT_SCHED:
; copy the 512 bit block to the first 512 bits of the message schedule
mov eax,[esi]
; big endian to little endian
bswap eax
mov [edi],eax
add esi,4
add edi,4
sub dx,4
cmp dx,0
jg .INIT_SCHED
; iterate the hash value
stdcall SHA_224_256_Iterate
dec cx
jcxz .DONE
jmp .HASH_BLOCK
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Compute_SHA_256 uses esi edi eax ecx
; process the single 512 bit (64 byte) message block
; this function expects the message block to have the big endian byte ordering
stdcall Init_H_0_SHA_256
mov ecx,[nBlocks512]
lea esi,[MESSAGE]
.HASH_BLOCK:
lea edi,[Message_Schedule]
mov dx,64
.INIT_SCHED:
; copy the 512 bit block to the first 512 bits of the message schedule
mov eax,[esi]
; big endian to little endian
bswap eax
mov [edi],eax
add esi,4
add edi,4
sub dx,4
cmp dx,0
jg .INIT_SCHED
; iterate the hash value
stdcall SHA_224_256_Iterate
dec cx
jcxz .DONE
jmp .HASH_BLOCK
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc SHA_1_Iterate uses esi edi ebx ecx
; prepare the message schedule
; the first 16 words of the message schedule
; already contain the 512 bit message block
lea esi,[Message_Schedule]
lea edi,[Message_Schedule]
add esi,64
add edi,64
mov cx,16
.PREPARE:
; W[t] = ROTL(W[t-3] xor W[t-8] xor W[t-14] xor W[t-16])
mov eax,[esi-12]
xor eax,[esi-32]
xor eax,[esi-56]
xor eax,[esi-64]
rol eax,1
mov [edi],eax
add esi,4
add edi,4
inc cx
cmp cx,80
jl .PREPARE
; initialise a,b,c,d,e
lea esi,[H_0_1]
lea edi,[Temp_H]
mov eax,[esi]
mov [edi],eax
mov eax,[esi+4]
mov [edi+4],eax
mov eax,[esi+8]
mov [edi+8],eax
mov eax,[esi+12]
mov [edi+12],eax
mov eax,[esi+16]
mov [edi+16],eax
; compute the hash
xor ecx,ecx
mov cx,0
lea esi,[Temp_H]
lea edi,[Message_Schedule]
.HASH:
; T = ROTL(a,5)
mov eax,[esi]
rol eax,5
; T += e
add eax,[esi+16]
mov edx,ecx
shl edx,2
; T += W[t]
add eax,[edi+edx]
.0_19:
cmp cx,19
jg .20_39
; add Kt
add eax,0x5a827999
; f(t) = Ch(b,c,d) = (b and c) xor (not(b) and d)
; calc f(t)(b,c,d)
mov ebx,[esi+4]
and ebx,[esi+8]
mov edx,[esi+4]
not edx
and edx,[esi+12]
xor edx,ebx
; add f(t) to T
add eax,edx
jmp .NEXT
.20_39:
cmp cx,39
jg .40_59
; add Kt
add eax,0x6ed9eba1
; f(t) = Parity(b,c,d) = b xor c xor d
; calc f(t)(b,c,d)
mov edx,[esi+4]
xor edx,[esi+8]
xor edx,[esi+12]
; add f(t) to T
add eax,edx
jmp .NEXT
.40_59:
cmp cx,59
jg .60_79
; add Kt
add eax,0x8f1bbcdc
; f(t) = Maj(b,c,d) = (b and c) xor (b and d) xor (c and d)
; calc f(t)(b,c,d)
mov ebx,[esi+4]
and ebx,[esi+8]
mov edx,[esi+4]
and edx,[esi+12]
xor edx,ebx
mov ebx,[esi+8]
and ebx,[esi+12]
xor edx,ebx
; add f(t) to T
add eax,edx
jmp .NEXT
.60_79:
; add Kt
add eax,0xca62c1d6
; f(t) = Parity(b,c,d) = b xor c xor d
; calc f(t)(b,c,d)
mov edx,[esi+4]
xor edx,[esi+8]
xor edx,[esi+12]
; add f(t) to T
add eax,edx
.NEXT:
; e = d
mov edx,[esi+12]
mov [esi+16],edx
; d = c
mov edx,[esi+8]
mov [esi+12],edx
; c = ROTL(30,b)
mov edx,[esi+4]
rol edx,30
mov [esi+8],edx
; b = a
mov edx,[esi]
mov [esi+4],edx
; a = T
mov [esi],eax
inc cx
cmp cx,80
jl .HASH
.UPDATE:
; add a,b,c,d,e to the hash
lea esi,[Temp_H]
lea edi,[H_0_1]
mov eax,[edi]
add eax,[esi]
mov [edi],eax
mov eax,[edi+4]
add eax,[esi+4]
mov [edi+4],eax
mov eax,[edi+8]
add eax,[esi+8]
mov [edi+8],eax
mov eax,[edi+12]
add eax,[esi+12]
mov [edi+12],eax
mov eax,[edi+16]
add eax,[esi+16]
mov [edi+16],eax
ret
endp
; -------------------------------------------------------------------------------------
proc SHA_224_256_Iterate uses esi edi ebx ecx
locals
T1 dd 0
T2 dd 0
endl
; prepare the message schedule
; the first 16 words of the message schedule
; already contain the 512 bit message block
lea esi,[Message_Schedule]
lea edi,[Message_Schedule]
add esi,64
add edi,64
mov cx,16
.PREPARE:
; W[t] = W[t-7] + W[t-16] + sigma_256_1(W[t-2]) + sigma_256_0(W[t-15])
; W[t-7]
mov eax,[esi-28]
; W[t-16]
add eax,[esi-64]
mov [edi],eax
; SHR(W(t-2),10)
mov edx,[esi-8]
shr edx,10
mov eax,edx
; ROTR(W(t-2),17)
mov edx,[esi-8]
ror edx,17
xor eax,edx
; ROTR(W(t-2),17)
mov edx,[esi-8]
ror edx,19
xor eax,edx
add [edi],eax
; SHR(W(t-15),3)
mov edx,[esi-60]
shr edx,3
mov eax,edx
; ROTR(W(t-15),7)
mov edx,[esi-60]
ror edx,7
xor eax,edx
; ROTR(W(t-15),18)
mov edx,[esi-60]
ror edx,18
xor eax,edx
add [edi],eax
add esi,4
add edi,4
inc cx
cmp cx,64
jl .PREPARE
; initialise a,b,c,d,e,f,g,h
lea esi,[H_0_256]
lea edi,[Temp_H]
mov eax,[esi]
mov [edi],eax
mov eax,[esi+4]
mov [edi+4],eax
mov eax,[esi+8]
mov [edi+8],eax
mov eax,[esi+12]
mov [edi+12],eax
mov eax,[esi+16]
mov [edi+16],eax
mov eax,[esi+20]
mov [edi+20],eax
mov eax,[esi+24]
mov [edi+24],eax
mov eax,[esi+28]
mov [edi+28],eax
; compute the hash
xor ecx,ecx
mov cx,0
lea esi,[Temp_H]
lea edi,[Message_Schedule]
lea ebx,[SHA_224_256_Kt]
.HASH:
; T1 = h
mov eax,[esi+28]
; T1 += W[t]
mov edx,ecx
shl edx,2
add eax,[edi+edx]
; T1 += Kt
add eax,[ebx+edx]
mov [T1],eax
; T1 += Ch(e,f,g) = (e and f) xor (not(e) and g)
mov eax,[esi+16]
and eax,[esi+20]
mov edx,[esi+16]
not edx
and edx,[esi+24]
xor eax,edx
add [T1],eax
; T1 += SIGMA_256_1(e) = ROTR(e,6) xor ROTR(e,11) xor ROTR(e,25)
mov eax,[esi+16]
ror eax,6
mov edx,[esi+16]
ror edx,11
xor eax,edx
mov edx,[esi+16]
ror edx,25
xor eax,edx
add [T1],eax
; T2 = SIGMA_256_0(a) = ROTR(a,2) xor ROTR(a,13) xor ROTR(a,22)
mov eax,[esi]
ror eax,2
mov edx,[esi]
ror edx,13
xor eax,edx
mov edx,[esi]
ror edx,22
xor eax,edx
mov [T2],eax
; T2 += Maj(a,b,c) = (a and b) xor (a and c) xor (b and c)
mov eax,[esi]
and eax,[esi+4]
mov edx,[esi]
and edx,[esi+8]
xor eax,edx
mov edx,[esi+4]
and edx,[esi+8]
xor eax,edx
add [T2],eax
; h = g
mov edx,[esi+24]
mov [esi+28],edx
; g = f
mov edx,[esi+20]
mov [esi+24],edx
; f = e
mov edx,[esi+16]
mov [esi+20],edx
; e = d + T1
mov edx,[T1]
add edx,[esi+12]
mov [esi+16],edx
; d = c
mov edx,[esi+8]
mov [esi+12],edx
; c = b
mov edx,[esi+4]
mov [esi+8],edx
; b = a
mov edx,[esi]
mov [esi+4],edx
; a = T1 + T2
mov edx,[T1]
add edx,[T2]
mov [esi],edx
inc cx
cmp cx,64
jl .HASH
.UPDATE:
; add a,b,c,d,e,f,g,h to the hash
lea esi,[Temp_H]
lea edi,[H_0_256]
mov eax,[edi]
add eax,[esi]
mov [edi],eax
mov eax,[edi+4]
add eax,[esi+4]
mov [edi+4],eax
mov eax,[edi+8]
add eax,[esi+8]
mov [edi+8],eax
mov eax,[edi+12]
add eax,[esi+12]
mov [edi+12],eax
mov eax,[edi+16]
add eax,[esi+16]
mov [edi+16],eax
mov eax,[edi+20]
add eax,[esi+20]
mov [edi+20],eax
mov eax,[edi+24]
add eax,[esi+24]
mov [edi+24],eax
mov eax,[edi+28]
add eax,[esi+28]
mov [edi+28],eax
ret
endp
; -------------------------------------------------------------------------------------
; generate the small prime
; -------------------------------------------------------------------------------------
proc ST_Random_Small_Prime
; generate the small random prime c0 (of length less than 33 bits)
locals
length dw 0
l_count dw 0
endl
; length is passed in AX (less than 33 bits)
cmp ax,33
jge .FAILURE
cmp ax,1
jle .FAILURE
; store the length
mov [length],ax
.HASH:
lea esi,[HashInteger]
lea edi,[Prime_c0]
cmp [DSA_N],160
je .SHA_1
cmp [DSA_N],224
je .SHA_224
cmp [DSA_N],256
je .SHA_256
jmp .FAILURE
.SHA_1:
; c = Hash(Prime_Seed) xor Hash(Prime_Seed + 1)
stdcall HashSeed_SHA_1
mov eax,[esi]
mov [edi],eax
stdcall IncrementSeed
stdcall HashSeed_SHA_1
mov eax,[esi]
xor [edi],eax
jmp .ADJUST_C
.SHA_224:
; c = Hash(Prime_Seed) xor Hash(Prime_Seed + 1)
stdcall HashSeed_SHA_224
mov eax,[esi]
mov [edi],eax
stdcall IncrementSeed
stdcall HashSeed_SHA_224
mov eax,[esi]
xor [edi],eax
jmp .ADJUST_C
.SHA_256:
; c = Hash(Prime_Seed) xor Hash(Prime_Seed + 1)
stdcall HashSeed_SHA_256
mov eax,[esi]
mov [edi],eax
stdcall IncrementSeed
stdcall HashSeed_SHA_256
mov eax,[esi]
xor [edi],eax
.ADJUST_C:
; c = 2^(length-1) + c mod 2^(length-1)
; 2^(length-1) = shl(1,length-1)
; c mod 2^(length-1) = c and (shl(1,length-1) - 1)
mov cx,[length]
; CL = length - 1
dec cx
; EAX = 2^(length-1)
mov eax,1
shl eax,cl
dec eax
and [edi],eax
inc eax
or [edi],eax
; set c to the least odd integer gte c
or [edi],dword 1
; increment counters and prime seed
inc word [l_count]
inc word [Counter]
stdcall IncrementSeed
stdcall TestSmallPrime
cmp al,1
je .SUCCESS
; check: local counter greater than (4 x length)
mov ax,[length]
shl ax,2
cmp ax,[l_count]
jle .FAILURE
jmp .HASH
.SUCCESS:
; copy to Last_c0
lea edi,[Last_c0]
stdcall ZeroHexBuffer
mov eax,[Prime_c0]
mov [edi],eax
mov eax,1
jmp .DONE
.FAILURE:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
; sieve to test candidate small primes
; -------------------------------------------------------------------------------------
proc CalcSieve uses esi edi ebx ecx
lea esi,[FactorBase]
lea edi,[FactorBase]
xor ecx,ecx
.CLEAR:
mov [edi+ecx],byte 0
inc cx
cmp cx,4096
jl .CLEAR
; Factor Base array: 4096 bytes = 32768 bits
; all the odd numbers from 1 to 65535
; bit_index = 0 to 32767
; 1 at bit_index 0 divides everything:
mov [edi],byte 1
; EBX = bit_index
; number = 1 + (2 x bit_index)
xor ebx,ebx
; start at bit_index = 1 (3)
inc ebx
.SIEVE:
mov edx,ebx
; EAX = 1 + (bit_index x 2)
mov eax,ebx
shl eax,1
inc eax
.SET_1:
; mark as composite by setting the bit to 1
add edx,eax
cmp edx,32767
jg .NEXT
; EDX gives the bit index, set the bit at this index to 1
; get the byte index
mov ecx,edx
shr ecx,3
mov edi,esi
add edi,ecx
; get the bit index
mov ecx,edx
and ecx,7
mov ch,1
shl ch,cl
; set the bit
or [edi],ch
jmp .SET_1
.NEXT:
inc ebx
cmp ebx,32767
jl .SIEVE
ret
endp
; -------------------------------------------------------------------------------------
proc TestSmallPrime uses esi edi ebx ecx
; test the candidate value c0 for primality
; result returned in AL
locals
bit db 0
bit_index dw 0
endl
; divide by each prime number in the FactorBase array
lea esi,[FactorBase]
xor ecx,ecx
.NEXT:
; get the byte
mov dl,[esi+ecx]
.FIND:
; find the next prime number in FactorBase
; test each bit in the byte
shr byte dl,1
jc .NEXT_BIT
; the bit is 0, so get the number
; number = 1 + (2 x bit_index)
; put the number into BX
mov bx,[bit_index]
shl bx,1
inc bx
.TEST:
mov eax,[Prime_c0]
; calculate EAX mod BX
stdcall Mod32
; remainder is in EAX, candidate not a prime if 0
cmp eax,0
je .NOT_PRIME
.NEXT_BIT:
; get the next bit
inc word [bit_index]
inc byte [bit]
cmp [bit],8
jl .FIND
.NEXT_BYTE:
mov [bit],byte 0
inc cx
cmp cx,4096
jl .NEXT
; candidate is a prime
mov eax,1
jmp .DONE
.NOT_PRIME:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc Mod32 uses edx
; compute EAX mod BX
; result returned in EAX
mov dx,bx
; make sure upper bytes of EBX are zero
xor ebx,ebx
mov bx,dx
xor edx,edx
; divide EDX:EAX by EBX
div ebx
; remainder in EDX
mov eax,edx
ret
endp
; -------------------------------------------------------------------------------------
proc HexToDec uses ecx edx
; convert the hex number in AX to a decimal string
; EDI is the destination string
; EDI is set outside of this procedure
locals
power db 4
digit db 0
endl
; the largest number that AX can hold is 65536
; so start with 10 to the power of 4
.CONVERT:
mov cl,[power]
stdcall Power_of_Ten
mov [digit],byte 0
.SUB:
; subtract powers of ten to get the left most decimal digit
cmp ax,dx
jl .NEXT
sub ax,dx
inc [digit]
jmp .SUB
.NEXT:
; add the digit to the output string
mov bl,[digit]
mov [edi],bl
add [edi],byte 48
inc edi
dec [power]
cmp [power],0
jge .CONVERT
mov [edi],byte 32
inc edi
ret
endp
; -------------------------------------------------------------------------------------
proc Power_of_Ten
; the exponent is passed in CL
; the result is returned in EDX
; EDX = 10 ^ CL
mov edx,1
.x10:
cmp cl,0
je .DONE
; multiply EDX by 10
mov ebx,edx
shl edx,3
shl ebx,1
add edx,ebx
dec cl
jmp .x10
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc StartOver
; reset everything
mov [Qgen_counter],word 0
mov [P0gen_counter],word 0
mov [Pgen_counter],word 0
mov [Prime_c],dword 0
mov [Prime_c0],dword 0
mov dx,32
lea edi,[First_Seed]
stdcall ZeroBuffer
lea edi,[Prime_Seed]
stdcall ZeroBuffer
lea edi,[Q_Seed]
stdcall ZeroBuffer
lea edi,[P0_Seed]
stdcall ZeroBuffer
lea edi,[P_Seed]
stdcall ZeroBuffer
lea edi,[Prime_Q]
stdcall ZeroBuffer
mov dx,200
lea edi,[Prime_P0]
stdcall ZeroBuffer
lea edi,[Candidate]
stdcall ZeroHexBuffer
lea edi,[First_Candidate]
stdcall ZeroHexBuffer
lea edi,[Last_x]
stdcall ZeroHexBuffer
lea edi,[Last_c0]
stdcall ZeroHexBuffer
lea edi,[Current_t]
stdcall ZeroHexBuffer
lea edi,[Current_z]
stdcall ZeroHexBuffer
lea edi,[Prime_P]
stdcall ZeroHexBuffer
ret
endp
; -------------------------------------------------------------------------------------
; miscellaneous functions
; -------------------------------------------------------------------------------------
proc IsShiftBfZero uses edi
; is ShiftBf zero ?
lea edi,[ShiftBf]
stdcall IsDblHexZero
ret
endp
; -------------------------------------------------------------------------------------
proc Update_Last_c0 uses esi edi ecx
; update Last_c0 from the candidate prime
lea esi,[Candidate]
lea edi,[Last_c0]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc SaveFirstCandidate uses esi edi ecx
; save the first candidate
lea esi,[Candidate]
lea edi,[First_Candidate]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc IsPrimeQZero uses edi ecx
; is the prime q zero ?
lea edi,[Prime_Q]
xor ecx,ecx
.TEST:
cmp [edi+ecx],byte 0
jne .NON_ZERO
inc cx
cmp cx,32
jl .TEST
; q is zero if the loop exits here
mov al,1
jmp .DONE
.NON_ZERO:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc IsPrimeP0Zero uses edi ecx
; is the prime p0 zero ?
lea edi,[Prime_P0]
xor ecx,ecx
.TEST:
cmp [edi+ecx],byte 0
jne .NON_ZERO
inc cx
cmp cx,200
jl .TEST
; p0 is zero if the loop exits here
mov al,1
jmp .DONE
.NON_ZERO:
xor eax,eax
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc ClearTempBuffer uses edi
; clear TempBf
lea edi,[TempBf]
stdcall ZeroHexBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc CopyToTempBuffer uses edi ecx
; copy from ESI to the temp buffer
; ESI is not modified
lea edi,[TempBf]
xor ecx,ecx
.COPY:
mov al,[esi+ecx]
mov [edi+ecx],al
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyFromTempBuffer uses esi ecx
; copy to EDI from the temp buffer
; EDI is not modified
lea esi,[TempBf]
xor ecx,ecx
.COPY:
mov al,[esi+ecx]
mov [edi+ecx],al
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc ClearCandidate uses edi
; clear the candidate prime
lea edi,[Candidate]
stdcall ZeroHexBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc CopyQToTempBf uses esi edi ecx
; copy q to TempBf
lea esi,[Prime_Q]
lea edi,[TempBf]
stdcall ZeroHexBuffer
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,32
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyP0ToExpBf uses esi edi ecx
; copy p0 to ExpBf
lea esi,[Prime_P0]
lea edi,[ExpBf]
stdcall ZeroHexBuffer
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,200
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyP0ToShiftBf uses esi edi ecx
; copy p0 to ShiftBf
lea esi,[Prime_P0]
lea edi,[ShiftBf]
stdcall ZeroDoubleHexBuffer
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,200
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyToBaseBf uses edi ecx
; copy ESI to BaseBf
; ESI is set outside of this procedure
lea edi,[BaseBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyToExpBf uses edi ecx
; copy ESI to ExpBf
; ESI is set outside of this procedure
lea edi,[ExpBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyToModBf uses edi ecx
; copy ESI to ModBf
; ESI is set outside of this procedure
lea edi,[ModBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc XchgProductBfShiftBf uses esi edi ecx
; swap the values in ProductBf and ShiftBf
lea esi,[ProductBf]
lea edi,[ShiftBf]
xor ecx,ecx
.SWAP:
mov dl,[esi+ecx]
mov bl,[edi+ecx]
mov [edi+ecx],dl
mov [esi+ecx],bl
inc cx
cmp cx,DBL_HEX_LEN
jl .SWAP
ret
endp
; -------------------------------------------------------------------------------------
proc IsExpBfZero uses edi
; is ExpBf equal to zero ?
lea edi,[ExpBf]
stdcall IsHexZero
ret
endp
; -------------------------------------------------------------------------------------
proc IsModBfZero uses edi
; is ModBf equal to zero ?
lea edi,[ModBf]
stdcall IsHexZero
ret
endp
; -------------------------------------------------------------------------------------
proc IsProductBfZero uses edi
; is the hex value in ProductBf zero ?
lea edi,[ProductBf]
stdcall IsDblHexZero
ret
endp
; -------------------------------------------------------------------------------------
proc CopyProductBfToShiftBf uses esi edi ecx
; copy ProductBf to ShiftBf
lea esi,[ProductBf]
lea edi,[ShiftBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,DBL_HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc CopyProductBfToTempBf uses esi edi ecx
; copy ProductBf to TempBf
lea esi,[ProductBf]
lea edi,[TempBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc ZeroQuotientBf uses edi
; zero the quotient buffer
lea edi,[QuotientBf]
stdcall ZeroHexBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc ZeroShiftBf uses edi
; zero the shift buffer
lea edi,[ShiftBf]
stdcall ZeroDoubleHexBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc CopyModBfToShiftBf uses esi
; copy ModBf to ShiftBf
lea esi,[ModBf]
stdcall CopyToShiftBf
ret
endp
; -------------------------------------------------------------------------------------
proc CopyBaseBfToProductBf uses esi
; copy BaseBf to ProductBf
lea esi,[BaseBf]
stdcall CopyToProductBf
ret
endp
; -------------------------------------------------------------------------------------
proc CopyToShiftBf uses edi ecx
; copy ESI to ShiftBf
; ESI is of length HEX_LEN
; ESI is set outside of this procedure
lea edi,[ShiftBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
.ZERO:
; zero the upper bytes of ShiftBf
mov [edi+ecx],byte 0
inc cx
cmp cx,DBL_HEX_LEN
jl .ZERO
ret
endp
; -------------------------------------------------------------------------------------
proc ZeroProductBf uses edi
; zero the product buffer
lea edi,[ProductBf]
stdcall ZeroDoubleHexBuffer
ret
endp
; -------------------------------------------------------------------------------------
proc CopyToProductBf uses edi ecx
; copy ESI to ProductBf
; ESI is of length HEX_LEN
; ESI is set outside of this procedure
lea edi,[ProductBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
.ZERO:
; zero the upper bytes of ProductBf
mov [edi+ecx],byte 0
inc cx
cmp cx,DBL_HEX_LEN
jl .ZERO
ret
endp
; -------------------------------------------------------------------------------------
proc CopyFromProductBf uses esi ecx
; copy from ProductBf to EDI
; EDI is of length HEX_LEN
; EDI is set outside of this procedure
lea esi,[ProductBf]
xor ecx,ecx
.COPY:
mov dl,[esi+ecx]
mov [edi+ecx],dl
inc cx
cmp cx,HEX_LEN
jl .COPY
ret
endp
; -------------------------------------------------------------------------------------
proc IsProductBfLessThanShiftBf uses esi edi ecx
; is ProductBf less than ShiftBf
lea esi,[ShiftBf]
lea edi,[ProductBf]
xor ecx,ecx
mov cx,DBL_HEX_LEN-1
.COMPARE:
mov dl,[esi+ecx]
cmp [edi+ecx],dl
jb .LT
ja .GTE
dec cx
cmp cx,0
jge .COMPARE
; if the loop exits here, the values are equal
.GTE:
xor eax,eax
jmp .DONE
.LT:
mov al,1
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
proc ZeroBuffer uses ecx
; clear the buffer (EDI)
; size passed in DX
xor ecx,ecx
.CLEAR:
mov [edi+ecx],byte 0
inc cx
cmp cx,dx
jl .CLEAR
ret
endp
; -------------------------------------------------------------------------------------
proc ZeroHexBuffer uses ecx
; zero the hex value in memory
; EDI is set outside of this procedure
xor ecx,ecx
.ZERO:
mov [edi+ecx],byte 0
inc cx
cmp cx,HEX_LEN
jl .ZERO
ret
endp
; -------------------------------------------------------------------------------------
proc ZeroDoubleHexBuffer uses ecx
; zero the double hex value in memory
; EDI is set outside of this procedure
xor ecx,ecx
.ZERO:
mov [edi+ecx],byte 0
inc cx
cmp cx,DBL_HEX_LEN
jl .ZERO
ret
endp
; -------------------------------------------------------------------------------------
proc AddStringToEDI
; print a string to the EDI buffer
; ESI and EDI are set outside of this procedure
.PRINT:
mov dl,[esi]
cmp dl,0
je .DONE
mov [edi],dl
inc esi
inc edi
jmp .PRINT
.DONE:
ret
endp
; -------------------------------------------------------------------------------------
section '.idata' import data readable writeable
library kernel,'KERNEL32.DLL',\
user,'USER32.DLL'
import kernel,\
GetModuleHandle,'GetModuleHandleA',\
ExitProcess,'ExitProcess'
import user,\
DialogBoxParam,'DialogBoxParamA',\
SetDlgItemText,'SetDlgItemTextA',\
GetDlgItemText,'GetDlgItemTextA',\
EndDialog,'EndDialog'
; -------------------------------------------------------------------------------------
section '.data' readable writeable
ShiftBf rb DBL_HEX_LEN
ProductBf rb DBL_HEX_LEN
QuotientBf rb HEX_LEN
TempBf rb HEX_LEN
BaseBf rb HEX_LEN
ExpBf rb HEX_LEN
ModBf rb HEX_LEN
DSA_N dw 160
DSA_L dw 1024
First_Seed rb 32
Prime_Seed rb 32
Q_Seed rb 32
P0_Seed rb 32
P_Seed rb 32
BitString rb 32
HashInteger rb 32
Prime_c dd 0
Prime_c0 dd 0
Candidate rb 400
First_Candidate rb 400
Last_c0 rb 400
Last_x rb 400
Current_t rb 400
Current_z rb 400
qp0x2 rb 400
Prime_Q rb 32
Prime_P0 rb 200
Prime_P rb 400
bfDisplay rb BF_DISP_LEN
Qgen_counter dw 0
P0gen_counter dw 0
Pgen_counter dw 0
Counter dw 0
nErrorCode dw 0
bToggle db 0
; -------------------------------------------------------------------------------------
section '.hash' readable writeable
MESSAGE rb 64
BitLength dd 0
nBlocks512 dd 0
H_0_1 rd 5
H_0_256 rd 8
Message_Schedule rd 160
Temp_H rd 8
SHA_224_256_Kt dd 0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,\
0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,\
0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,\
0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,\
0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,\
0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,\
0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,\
0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,\
0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,\
0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,\
0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,\
0xd192e819,0xd6990624,0xf40e3585,0x106aa070,\
0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,\
0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,\
0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,\
0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
FactorBase rb 4096
szErrMessage_0 db "Unknown Error.",0
szErrMessage_1 db "Failed to generate the prime c0.",0
szErrMessage_2 db "Failed to generate the prime q.",0
szErrMessage_3 db "The prime q has not been generated.",0
szErrMessage_4 db "Failed to generate the prime p0.",0
szErrMessage_5 db "The prime p0 has not been generated.",0
szErrMessage_6 db "Failed to generate the prime p.",0
szQFoundMsg db "THE PRIME q HAS BEEN FOUND:",0
szP0FoundMsg db "THE PRIME p0 HAS BEEN FOUND:",0
szPFoundMsg db "THE PRIME p HAS BEEN FOUND:",0
szPQFoundMsg db "THE PRIMES p AND q HAVE BEEN FOUND:",0
; -------------------------------------------------------------------------------------
section '.rc' resource data readable
directory RT_DIALOG,dialogs
resource dialogs,IDD_THE_DIALOG,LANG_ENGLISH+SUBLANG_DEFAULT,the_dialog
dialog the_dialog,\
'DSA Primes',20,50,406,328,\
DS_MODALFRAME+WS_MINIMIZEBOX+WS_POPUP+WS_VISIBLE+WS_CAPTION+WS_SYSMENU,\
0,0,"Lucida Console",11
dialogitem 'EDIT',0,IDC_OUTPUT,11,14,309,255,ES_MULTILINE+ES_AUTOVSCROLL+ES_WANTRETURN+WS_VSCROLL+WS_BORDER+WS_VISIBLE,0
dialogitem 'EDIT',0,IDC_FIRST_SEED,10,298,320,14,ES_AUTOHSCROLL+WS_BORDER+WS_VISIBLE,0
dialogitem 'BUTTON',"Output",-1,6,3,320,276,BS_GROUPBOX+WS_VISIBLE,0
dialogitem 'BUTTON',"Action",-1,332,3,68,124,BS_GROUPBOX+WS_VISIBLE,0
dialogitem 'BUTTON',"First Seed",-1,6,284,394,37,BS_GROUPBOX+WS_VISIBLE,0
dialogitem 'BUTTON',"Select L, N",-1,332,132,68,147,BS_GROUPBOX+WS_VISIBLE,0
dialogitem 'BUTTON',"Generate q",IDC_GEN_Q,336,14,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"Generate p0",IDC_GEN_P0,336,32,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"Generate p",IDC_GEN_P,336,50,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"Generate All",IDC_GEN_ALL,336,68,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"Start Over",IDC_START_OVER,336,86,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"Toggle View",IDC_TOGGLE,336,104,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"Capture",IDC_CAPTURE,336,297,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"1024,160",IDC_BTN_1024_160,336,144,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"2048,224",IDC_BTN_2048_224,336,162,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"2048,256",IDC_BTN_2048_256,336,180,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
dialogitem 'BUTTON',"3072,256",IDC_BTN_3072_256,336,198,60,16,BS_PUSHBUTTON+WS_VISIBLE,0
enddialog
; -------------------------------------------------------------------------------------
|
Assembly Language Programming 