# Assembly Language Programming

## October 25, 2012

### Digital Signature Algorithm – Generating Large Prime Numbers

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:

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:

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 ; ------------------------------------------------------------------------------------- ```