I've spend the last few days reverse-engineering the password system in Dragon Quest (J) but I need some help in order to fully understand the system.

The two routines involved are, obviously, the routine encoding a password when you talk to the king and display it on screen. And the routine decoding a password from the password entry screen.

The password is made of 20 hiragana character, arranged in a 5/7/5/3 haiku fashion (this is purely cosmetic, it doesn't play a role for the computer). The game technically supports entering shorter passwords but they'll always be rejected. There is at least 8 known passwords which are known to be made of meaningful japanese words.

Each hiragana character represent 6-bit worth of data (range $00-$3f). The password length is then 20*6=120 bits of data.

The password encoding does the following :

- Store relevant data such as HP, EXP, equip list, etc... in a RAM array of 15 bytes (120 bits of data)
- 3 bits are also taken from the random number generator and store in the password, so there is actually groups of 8 randomly-selected passwords for each game state (why ?)
- Compute a 8-bit checksum and insert it in the first 8-bits
- Re-arrange the password from 15x8-bit words into 20x6-bit words
- Scramble the symbol so that each symbol is added with the previous symbol, and added with the constant #4 (overflow within 6-bit range)
- Convert 6-bit symbols to actual hiragana characters and prints them

- Password is rejected if length <20
- Symbols are de-scrambled by subracting from the previos symbol and subtracting a constant #4 (overflow within 6-bit range)
- The 20x6-bit words are re-arranged as 15x8-bit words
- The checksum is computed in the 14 last words, and should match the first word, if there's no match the password is rejected
- The relevant data from the password is stored into game state, with some sanity checks, which might also get the password rejected if something is inconsistant

1) How is the ckecksum computed. I have the code, but I wonder if that's a CRC checksum or something else, or just something random the programmers came up with

2) How in the world is it possible to have (at least) 8 meaningful pre-defined passwords with such a system ? I'd though with the 8-bit checksum defined in a clever way, at most one meaningful password could naturally come out of this. It cannot be a pure coincidence, but I checked and I didn't see any specific code to detect meaningful passwords like I'd have expected to !! I'm puzzled !

Now the disassembled code, for password decoding. It is stored in CHR-ROM bank #3 and loaded in RAM at runtime, which is why the automatically generated disassembler's labels are

*wrong adresses*.

Code: Select all

```
lbl_e376: ldx #$0
stx $42
- lda $1a,x ; read password
and #$c0
beq +
inc $42 ; $42 counts invalid characters in password
+ inx
cpx #$14
bne -
lda $42
beq +
jmp invalid_password ; I suppose the branch distance was too large ?
+ dex
- lda $1a,x
sec
sbc $19,x
sec
sbc #$4
and #$3f
sta $61,x ; De-scramble password symbols to $61-$71 zp buffer
dex
bne -
lda $1a ; I suppose the programmers weren't very skilled with 6502...
sec
sbc #$4
and #$3f
sta $61
lda #$0
sta $3c
tay
--- lda #$8
sta $40
-- ldx #$14
- ror $60,x ; rotate a password bit into carry
dex
bne -
php
lda $3c
lbl_e3ba: inc $3c
and #$7
cmp #$6 ; continue rotating until 6 bits are done
bcc lbl_e3c6 ; (the last 2 bits are ignored because always '0')
plp
jmp --
;--------------------
lbl_e3c6: plp
ror $3e ; the 6 meaningful bits are stored in the high 6 bits of $3e
dec $40
bne --
lda $3e
sta $51,y ; Store the password in 8-bits words to $51-$5f
lbl_e3d2: iny ; Player's password : 20 symbols x 6 bits = 120 bits
cpy #$f ; Computer's password : 15 bytes x 8 bits = 120 bits
bne ---
ldx #$0
stx $3c
stx $3d ; Clear the check sum
inx
-- ldy #$8
lda $51
sta $3e
- lda $3d
eor $3e
asl $3c
rol $3d ; Mysterious checksum algorithm
asl $3e
asl a
bcc +
lda $3c
eor #$21
sta $3c
lda $3d
eor #$10
sta $3d
+ dey
bne -
inx
cpx #$f
bne --
lda $3c ; Compare computer checksum
cmp $51 ; With the first 8-bit of password
beq Valid_password: ; Only valid if the same value !
Invalid_password:
lda #$66 ; This routine displays the dialogue box
sta $99 ; to tell the player the password is invalid
lda #$7
sta $9a
jsr lbl_544
jsr lbl_ab9b
jsr lbl_b8c3
lda $47
bne lbl_e416
jsr lbl_ab9b
jsr lbl_b8c3
lda $47
lsr a
bcc lbl_e420
jsr lbl_ab9b
jsr lbl_b8c3
lda $47
bne lbl_e42b
lda #$8c
sta $99
lda #$7
sta $9a
jsr lbl_544
jmp lbl_369
;--------------------
lbl_544:
lda #$a
lbl_e445: sta $97
sta $9d
lda #$f
sta $98
lda #$1
sta $9
jsr lbl_bd09
inc $99
bne lbl_e45a
inc $9a
lbl_e45a: dec $98
lda $98
cmp #$14
bne lbl_e451
rts
;--------------------
valid_password: lda $56 ; copies values from password buffer $51-$5f to real game values
lsr a
lsr a
jsr lbl_704
sta $b5 ; $B5 first name letter
lbl_e46c: lda $5e
lsr a
and #$3f
jsr lbl_704
sta $b6 ; $B6 2nd name letter
lda $53
and #$3f
jsr lbl_704
sta $b7 ; $B7 3rd name letter
lda $58
and #$3f
jsr lbl_704
sta $b8 ; $B8 4th name letter
lda $52
sta $ba
lda $5d
sta $bb ; $ba-$bb = experience
lda $55
sta $bc ; $bc-$bd = money
lda $5a
sta $bd
lda $59
sta $be ; equipment
lda $5f
sta $c1
lda $54
sta $c2
lda $5c
sta $c3
lda $57
sta $c4 ; $c1-$c4 = inventory
lda $5b
and #$f
sta $c0 ; $c0 = amount of herbs
lda $5b
lsr a
lsr a
lsr a
lsr a
sta $bf ; $bf = amount of keys
lda #$0
sta $df
lbl_e4be: sta $e4
sta $cf ; Quest progress, a huge mess
bit $53
bvc lbl_e4ca
lda #$4
sta $df
lbl_e4ca: lda $56
and #$2
sta $e4
lda $58
and #$c0
lbl_e4d4: ora $e4
sta $e4
lda $5e
bpl lbl_e4e0
lda #$10
sta $cf
lbl_e4e0: lda $5e
lsr a
bcc lbl_e4eb
lda $cf
ora #$20
sta $cf
lbl_e4eb: lda $df
ora #$8
sta $df
lda #$8
jsr lbl_de40
cmp #$ff
beq lbl_e500
lda $df
ora #$2
sta $df
lbl_e500: lda $c0
cmp #$7
bcs lbl_e516
lda $bf
cmp #$7
lbl_e50a: bcs lbl_e516 ; Whether >7 keys or herbs refuse password
lda #$f
jsr lbl_de40
cmp #$ff
bne lbl_e516
rts
;--------------------
lbl_e516: jmp lbl_50c
;--------------------
cmp #$1
bne lbl_e552
lda $c7
cmp #$13
bne lbl_e526
jmp lbl_413
;--------------------
lbl_e526: jsr lbl_6f1
inc $c7
lbl_e52b: inc $90
lda $c7
cmp #$5
beq lbl_e537
cmp #$11
bne lbl_e53c
lbl_e537: inc $90
jmp lbl_649
;--------------------
lbl_e53c: cmp #$c
bne lbl_e548
lda #$8
sta $90
lda #$a
lbl_e546: sta $92
lbl_e548: jsr lbl_6de
lda #$0
sta $4f
lbl_e54f: jmp lbl_413
;--------------------
lbl_e552: bcs lbl_e587
lda $c7
bne lbl_e55b
jmp lbl_413
;--------------------
lbl_e55b: jsr lbl_6f1
dec $c7
lbl_e560: dec $90
lda $c7
cmp #$10
beq lbl_e56c
cmp #$4
bne lbl_e571
lbl_e56c: dec $90
jmp lbl_67e
;--------------------
lbl_e571: cmp #$b
bne lbl_e57d
lda #$14
sta $90
lda #$7
lbl_e57b: sta $92
lbl_e57d: jsr lbl_6de
lda #$0
sta $4f
jmp lbl_413
;--------------------
lbl_e587: sec
sbc #$a
cmp #$cd
bcc lbl_e591
sec
sbc #$a1
lbl_e591: ldx $c7
sta $1a,x ; Store password character in buffer
lda $90
sta $3c
ldx $92
dex
dex
stx $3e
jsr lbl_ac9f
lda #$5f
sta $8
jsr lbl_aba4
lda $90
sta $97
lda $92
sta $98
dec $98
lda #$1
sta $9
lbl_e5b7: jsr lbl_bd18
lda $c7
cmp #$13
bne lbl_e5c3
jmp lbl_471
;--------------------
lbl_e5c3: jmp lbl_627
;--------------------
lda $8e
sta $3c
lda $8f
sta $3e
jsr lbl_ac9f
lda #$5f
sta $8
jsr lbl_aba4
lda #$0
sta $4f
rts
;--------------------
lda $90
sta $3c
lda $92
sta $3e
jsr lbl_ac9f
lda #$3d
sta $8
jsr lbl_aba4
rts
;--------------------
lda $90
sta $3c
lda $92
sta $3e
jsr lbl_ac9f
lda #$5f
sta $8
jsr lbl_aba4
rts
;-------------------- ; Retrives name's letter in $3c-$3f range which are special characters
cmp #$3c ; (why on earch didn't they just change CHR-ROM order to match this ?!)
lbl_e605: bne lbl_e60a
lda #$53 ; $3c becomes dakuten
rts
;--------------------
lbl_e60a: cmp #$3d
lbl_e60c: bne lbl_e611
lda #$54 ; $3d becomes handakuten
rts
;--------------------
lbl_e611: cmp #$3e
bne lbl_e618
lda #$4e ; $3e becomes dash
rts
;--------------------
lbl_e618: cmp #$3f
bne lbl_e61e ; $3f becomes space
lda #$5f
lbl_e61e: rts
;--------------------
```

Code: Select all

```
; This routine generates a password
lbl_ef69: lda $4
bne lbl_ef69 ; Wait for Vsync
lda $b7
jsr lbl_f0c6
sta $302
lda $b5
jsr lbl_f0c6
asl a ; Store name ($b5-$b8) in a strange scrambled way
asl a
sta $305
lda $b8
jsr lbl_f0c6
sta $307
lda $b6
jsr lbl_f0c6
asl a
sta $30d
lda $bb
sta $30c
lda $ba
sta $301 ; Store experience
lda $bc
sta $304
lda $bd
sta $309 ; Gold
lda $c2
sta $303
lda $c4
sta $306
lda $c3
sta $30b
lda $c1
sta $30e ; Items
lda $be
sta $308 ; Equipment
lda $bf
asl a
asl a
asl a
asl a
ora $c0
sta $30a ; Amount of herbs and keys
lda $df ; Quest progress, a huge mess
and #$4
beq lbl_efd6
lda #$40
ora $302
sta $302
lbl_efd6: lda $cf
and #$10
beq lbl_efe4
lda #$80
ora $30d
sta $30d
lbl_efe4: lda $cf
and #$20
beq lbl_eff2
lda #$1
ora $30d
sta $30d
lbl_eff2: lda $e4
and #$2
ora $305
sta $305
lda $e4
and #$40
ora $307
sta $307
jsr lbl_b0bf ; Trigger RNG
lda $95 ; Store 2 bits
and #$80
ora $302
sta $302
lda $95
and #$1
ora $305
sta $305
jsr lbl_b0bf ; Trigger RNG agian dnd store a 3rd bit
lda $95 ; I guess this is so that the king gives a semi-random
and #$80 ; password form 8 possible at a given game state
ora $307
sta $307 ; Password ready in $300-$30E
lda #$0
sta $3c
sta $3d ; Clear checksum
ldx #$1
-- ldy #$8
lda $300,x
sta $3e
- lda $3d
eor $3e
asl $3c
rol $3d
asl $3e
asl a
bcc +
lda $3c
eor #$21
sta $3c
lda $3d
eor #$10
sta $3d
+ dey
bne -
inx
cpx #$f
bne --
lda $3c ; check stored in the first 8-bits of password
sta $300
lda #$5f
ldx #$0
lbl_f063: sta $400,x ; clear the password (why ?)
inx
cpx #$1c
bne lbl_f063
lda #$fe
sta $40f
lda #$fc
sta $41b ; ??
lda #$0
sta $3c
sta $3e
lbl_f07b: lda $300 ; Take a password letter
and #$3f
clc
adc $3e ; Add to result of previous letter
clc
adc #$4
and #$3f ; Add 4 and keep result within 6 bits
sta $3e
jsr lbl_f0e2 ; Convert password symbol $00-$3f to actual letter
ldx $3c
sta $402,x ; Store next letter bits in the line buffer
inc $3c
lda $3c
cmp #$5 ; create spaces between words where necessary
beq lbl_f0c2
cmp #$15
beq lbl_f0c2
cmp #$d
beq lbl_f0be
cmp #$19
bne lbl_f07b
lda #$0
sta $99
lda #$4
sta $9a
jsr lbl_c45f ; Actually display the password in the text box.
lda #$ff
ldx #$0
lbl_f0b5: sta $400,x
inx
cpx #$20
bne lbl_f0b5
rts
;--------------------
lbl_f0be: inc $3c
inc $3c
lbl_f0c2: inc $3c
bne lbl_f07b ; always taken
;--------------------
lbl_f0c6: cmp #$53 ; Decode special caracters in name
bne lbl_f0cd ; dakuten, handakuten, dash and space
lda #$3c ; to be in $00-$3f range
rts
;--------------------
lbl_f0cd: cmp #$54
bne lbl_f0d4
lda #$3d
rts
;--------------------
lbl_f0d4: cmp #$4e
bne lbl_f0db
lda #$3e
rts
;--------------------
lbl_f0db: cmp #$5f
bne lbl_f0e1
lda #$3f
lbl_f0e1: rts
;--------------------
lbl_f0e2: ldy #$6
lbl_f0e4: ldx #$f
lbl_f0e6: ror $2ff,x ; rotate 6 bits out of the buffer
dex
bne lbl_f0e6
dey
bne lbl_f0e4
clc
adc #$a
cmp #$36 ; convert password symbol (in A) into a letter
bcc lbl_f0f9
clc
adc #$a1
lbl_f0f9: rts
```