SHA-1 implementation in Z80
This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's z80 & ez80 Assembly subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.

This forum is locked: you cannot post, reply to, or edit topics. Z80 & 68k Assembly => z80 & ez80 Assembly
SHA-1 implementation in Z80
United-TI Archives -> Z80 & 68k Assembly
 
    »
» View previous topic :: View next topic  
Author Message
Goplat


Advanced Newbie


Joined: 26 Jun 2007
Posts: 95
Posted: 07 Dec 2010 09:31:46 pm    Post subject:
This took a lot longer than I expected, darn 32-bit operations :(


Code:

   .org $9D93
   .db $BB, $6D

   jp main

sha1_hash:
   .db $67,$45,$23,$01
   .db $EF,$CD,$AB,$89
   .db $98,$BA,$DC,$FE
   .db $10,$32,$54,$76
   .db $C3,$D2,$E1,$F0
sha1_length:
   .db $00,$00,$00,$00
   .db $00,$00,$00,$00
sha1_block_ptr:
   .dw sha1_block

sha1_pad:
   ; append the bit '1' to the message
   ; append 0 <= k < 512 bits '0', so that the resulting message length (in bits)
   ;    is congruent to 448 = -64 (mod 512)
   ld a, $80
sha1_pad_zero:
   call sha1_add_byte_no_length
   ld a, (sha1_block_ptr)
   cp (sha1_block+56) & 255
   ld a, $00
   jr nz, sha1_pad_zero
   ; append length of message (before padding), in bits, as 64-bit big-endian integer
   ld hl, sha1_length
   ld de, (sha1_block_ptr)
   ld bc, 8
   ldir
   jr sha1_process_block

sha1_add_byte:
   push af
   ld hl, sha1_length+7
   ld a, (hl)
   add a, 8
   ld (hl), a
   jr nc, _length_ok
_length_inc:
   dec hl
   inc (hl)
   jr z, _length_inc
_length_ok:
   pop af

sha1_add_byte_no_length:
   ld de, (sha1_block_ptr)
   ld (de), a
   inc de
   ld (sha1_block_ptr), de
   ld a, e
   cp (sha1_block+64) & 255
   ret nz
sha1_process_block:

   ;    Extend the sixteen 32-bit words into eighty 32-bit words:
   ;    for i from 16 to 79
   ;        w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
   ld ix, sha1_block+63
   ld c, 64
_extend:
   ld b, 4
_extend_inner:
   inc ix
   ld a, (ix-12)
   xor (ix-32)
   xor (ix-56)
   xor (ix-64)
   ld (ix), a
   djnz _extend_inner
   push ix
   pop hl
   ld a, (ix-3)
   rlca
   rl (hl) \ dec hl
   rl (hl) \ dec hl
   rl (hl) \ dec hl
   rl (hl) \ dec hl
   dec c
   jr nz, _extend

   ;    Initialize hash value for this chunk:
   ;    a = h0
   ;    b = h1
   ;    c = h2
   ;    d = h3
   ;    e = h4
   ld hl, sha1_hash
   ld de, sha1_a
   ld bc, 20
   ldir

   ;    Main loop
   ld hl, sha1_block-1 \ ld (sha1_block_ptr), hl
   ld hl, operation_mux \ call sha1_20rounds \ .db $5A,$82,$79,$99
   ld hl, operation_xor \ call sha1_20rounds \ .db $6E,$D9,$EB,$A1
   ld hl, operation_maj \ call sha1_20rounds \ .db $8F,$1B,$BC,$DC
   ld hl, operation_xor \ call sha1_20rounds \ .db $CA,$62,$C1,$D6

   ;    Add this chunk's hash to result so far
   ;    h0 += a
   ;    h1 += b
   ;    h2 += c
   ;    h3 += d
   ;    h4 += e
   ld de, sha1_hash+19
   ld hl, sha1_a+19
   ld c, 5
_add_result:
   call add_32bits
   dec c
   jr nz, _add_result

   ld hl, sha1_block
   ld (sha1_block_ptr), hl
   ret

sha1_20rounds:
   ld (sha1_f_op_ptr), hl
   pop hl
   ld de, sha1_k
   ld bc, 4
   ldir
   push hl

   ld b, 20
_rounds:
   push bc

   ; f = <some operation involving b, c, and d>
   call do_f_operation

   ; temp = (a leftrotate 5) + f + e + k + w[i]
   ld hl, sha1_a
   ld de, sha1_temp
   ld bc, 4
   ldir
   ld a, (sha1_temp)
   rrca
   rrca
   rrca
   rrca
   ld hl, sha1_temp+3
   rld \ rl (hl) \ dec hl
   rld \ rl (hl) \ dec hl
   rld \ rl (hl) \ dec hl
   rld \ rl (hl)
   ld hl, sha1_k+3
   call add_to_temp ; k
   call add_to_temp ; f
   call add_to_temp ; e
   ld hl, (sha1_block_ptr)
   inc hl
   inc hl
   inc hl
   inc hl
   ld (sha1_block_ptr), hl
   call add_to_temp

   ; e = d
   ; d = c
   ; c = b leftrotate 30
   ; b = a
   ; a = temp
   ld hl, sha1_d+3
   ld de, sha1_e+3
   ld bc, 20
   lddr
   ld a, (sha1_c+3)
   ld b, 2
_ror2:
   ld hl, sha1_c
   rrca
   rr (hl) \ inc hl
   rr (hl) \ inc hl
   rr (hl) \ inc hl
   rr (hl)
   djnz _ror2

   pop bc
   djnz _rounds
   ret

do_f_operation:
   ld ix, sha1_a
   ld hl, (sha1_f_op_ptr)
   ld b, 4
   jp (hl)
operation_mux:
   ; f = (b & c) | (~b & d) = ((c ^ d) & 8) ^ d
   ld a, (ix+8)
   xor (ix+12)
   and (ix+4)
   xor (ix+12)
   ld (ix+20), a
   inc ix
   djnz operation_mux
   ret
operation_xor:
   ; f = b ^ c ^ d
   ld a, (ix+4)
   xor (ix+8)
   xor (ix+12)
   ld (ix+20), a
   inc ix
   djnz operation_xor
   ret
operation_maj:
   ; f = (b & c) | (b & d) | (c & d)
   ld c, (ix+4)
   ld d, (ix+8)
   ld e, (ix+12)
   ld a, c
   and d
   ld h, a
   ld a, c
   and e
   ld l, a
   ld a, d
   and e
   or h
   or l
   ld (ix+20), a
   inc ix
   djnz operation_maj
   ret

add_to_temp:
   ld de, sha1_temp+3
add_32bits:
   ld b, 4
   or a
_add_loop:
   ld a, (de)
   adc a, (hl)
   ld (de), a
   dec de
   dec hl
   djnz _add_loop
   ret

sha1_block:
   .org $+320

sha1_f_op_ptr:
   .org $+2

; Keep these contiguous
sha1_temp = $
sha1_a    = $+4
sha1_b    = $+8
sha1_c    = $+12
sha1_d    = $+16
sha1_e    = $+20
sha1_f    = $+24
sha1_k    = $+28
   .org $+32

main:
   ld hl, message
_msgloop:
   ld a, (hl)
   or a
   jr z, _msgdone
   push hl
   call sha1_add_byte
   pop hl
   inc hl
   jr _msgloop
_msgdone:
   call sha1_pad

   ; Display the SHA-1 in hex
   ld hl, sha1_hash
   ld b, 20
_output:
   ld a, (hl)
   rrca
   rrca
   rrca
   rrca
   and $0F
   cp $0A
   sbc a, $69
   daa
   rst 28h \ .dw $4504
   ld a, (hl)
   and $0F
   cp $0A
   sbc a, $69
   daa
   rst 28h \ .dw $4504
   inc hl
   djnz _output

   ret

message:
   .db "The quick brown fox jumps over the lazy dog",0
   ; should have SHA-1 of: 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12

   .end
Back to top
Xeda112358


Active Member


Joined: 19 May 2009
Posts: 520
Posted: 08 Dec 2010 01:37:28 am    Post subject:
So, um, forgive my lack of exposure, but what is SHA-1? Some form of encryption method?
Back to top
Galandros


Active Member


Joined: 29 Aug 2008
Posts: 565
Posted: 08 Dec 2010 04:37:41 pm    Post subject:
Large code and if someone could think implementing quicksort in z80 could be an experiment this passes all levels of extreme experimentation.

The TIOS implements MD5 but I have read it was hardware (non z80 CPU of course) assisted. I hope TI doesn't get idea of updated OS with new keys and SHA1 hash. xD

And yes, 32-bit operations in only 6 8-bit registers that form 3 16-bit registers pairs that aren't general purpose registers leads to much harder implementation.

ThunderBolt wrote:

So, um, forgive my lack of exposure, but what is SHA-1? Some form of encryption method?

It is not encryption method but is related to cryptography. It can be used as a cryptographic hash, a way to validate a fidedign source of information.


It can also be used as checksums instead of MD5, that has some known flaws, for file integrity. For this use it is named sha1sum and I don't know if there is difference in the algorithm between for cryptographic use and data integrity test.
Back to top
Xeda112358


Active Member


Joined: 19 May 2009
Posts: 520
Posted: 08 Dec 2010 11:05:21 pm    Post subject:
Okay, thanks. I don't really know much about technology and this kind of thing, so I try to learn a little at a time... I can program in hex, though! Lawlz
Back to top
Galandros


Active Member


Joined: 29 Aug 2008
Posts: 565
Posted: 13 Dec 2010 02:39:18 pm    Post subject:
ThunderBolt wrote:

Okay, thanks. I don't really know much about technology and this kind of thing, so I try to learn a little at a time... I can program in hex, though! Lawlz

I know because I like cryptography and read some things about it.

Giving another thought on SHA-1 on z80, it might be used for certifying software licenses I guess? This can be the main application because for a checksum CRC16 and CRC32 seem lighter and there is code on WikiTI for it.

Goplat do you mind me putting this code on WikiTI? http://wikiti.brandonw.net/index.php?title=WikiTI_Home
Back to top
Goplat


Advanced Newbie


Joined: 26 Jun 2007
Posts: 95
Posted: 13 Dec 2010 06:24:49 pm    Post subject:
Galandros wrote:

Goplat do you mind me putting this code on WikiTI? http://wikiti.brandonw.net/index.php?title=WikiTI_Home


If you do, please optimize the operation_ functions; now that I look at them again there's some room for improvement. operation_mux can save several tstates by saving (ix+12) in a register:

Code:

   ld a, (ix+8)
   ld c, (ix+12)
   xor c
   and (ix+4)
   xor c


and operation_maj can be improved a lot by using the distributive property that boolean "and" and "or" have with each other:

Code:

   ; f = (b & c) | (b & d) | (c & d)
   ;   = (b & c) | ((b | c) & d)
   ld c, (ix+4)
   ld d, (ix+8)
   ld a, c
   and d
   ld e, a
   ld a, c
   or d
   and (ix+12)
   or e
   ld (ix+20), a
Back to top
DigiTan
Unregistered HyperCam 2


Super Elite (Last Title)


Joined: 10 Nov 2003
Posts: 4468
Posted: 14 Dec 2010 11:07:06 am    Post subject:
Nothing beats a little cold, hard harsh. So can this detect file tampering as well?
Back to top
Display posts from previous:   
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
SHA-1 implementation in Z80
    »
» View previous topic :: View next topic  
Page 1 of 1 » All times are UTC - 5 Hours

 

Advertisement