A coding device, a decoding device, and an IC card capable of establishing highly reliable security are disclosed. A random number determining section 11, using a random number generating procedure selected with a random number generating procedure selecting section 10, determines a random number (a first secret key) C according to random number selecting information. On the other hand, an algorithm selecting section 13 selects a secret key code type of algorithm E according to algorithm selecting information. A secret key coding section 12, using the random number C and the algorithm E, converts data to be coded B into a secret key code sentence. After a publicized key coding section 15 converts the random number C and the algorithm selecting information into a publicized key code sentence, a combined code sentence forming section 14 forms a combined code sentence by combining together the secret key code sentence and the publicized key code sentence.