Patent ID: 8891759

Claim:
A cryptographic processing device, comprising: a private key storage unit which stores a private key d for elliptic curve cryptography; a random number generation unit which generates a signed or unsigned b-bit random value s; a memory storing instructions; and a processor which executes the instructions to provide a processing unit which reads the private key d from the private key storage unit, and with respect to a positive integer m where a relation u=mk+b holds true for a length u of a bit string D which is the private key d or a bit string obtained by modifying the private key d in such a way that a value of a most significant bit is 0, and a window size k, determines, by using the bit string D and the random value s, a window value w[i] which is a signed k-bit value corresponding to each i where 0≦i≦(m−1), a random value s[i] which is a signed b-bit value corresponding to each i where 0≦i≦(m−1), and a correction value g, under a constraint condition in which D = g + ∑ i = 0 m - 1 ⁢ ( 2 ki + b ⁢ w ⁡ [ i ] + 2 ki ⁢ s ⁡ [ i ] ) holds true, while determining each random value s[i] to be +s or −s.