Crypto
References
- Japanese Cryptography Beginners Book「 暗号技術入門（結城浩 Yuuki Hiroshi）」
- Picture liscence are from [http://sponge.noekeon.org](http://sponge.noekeon.org)
- Picture liscence are from [http://keccak.noekeon.org](http://keccak.noekeon.org)
- [Keccak tools](https://github.com/gvanas/KeccakTools) are open source tools by Gilles Van Assche.
# Basic keywords
## `symmetric cryptography`
***************************************************************
* *
* *
* encypt decrypt *
* *
* plaintext ----> cyphertext ----> plaintext *
* *
* *
* *
***************************************************************
encrypt() $ = $ decrypt()
These are the same.
- common-key cryptography
- secret-key cryptography
- shared-key cryptography
## `public-key cryptography`
encrypt() $ \neq $ decrypt()
- assymmetric cryptography
## hash
`one-way hash function` gives `integrity` with hashed value.
## message authentication code
this gives the authentication that the message which is sended is not changed by someone malicious.
## spoofing
## repudiation
$ \leftarrow $ `digital signature`
we can stop repudiation with `verify`ing digital signature.
# History
## Caesar cipher
アルファベットをずらすことで暗号化
***********************************************
* *
* *
* key: 3 *
* | *
* v *
* +---------+ *
* | Caesor | *
* yoshiko -->| Encrypt |---> BRVKNR *
* +---------+ *
* *
* *
***********************************************
~~~
if `brute-force attack`
then
success decrypt
with probability `1/26`!
~~~
## simple substition cypher
make map by character
|text|code|
|:---:|:---:|
|a|W|
|b|H|
|c|H|
|d|F|
|...|...|
|z|I|
keyspace is $ 26! = 26 \times 25 \times ... \times 1 $ large.
if plaintext is some meaning sentence,
then we can apply 頻度分析
e : most used character
e -> t -> a -> o -> i -> n -> s -> h ....
# Symmetric
## Vernam cypher
this is called `one time pad`
~~~
XOR(plaintext, key)
~~~
suppose key: midnight
~~~
m i d n i g h t
01101101 01101001 011000100 01101110 01101001 01100111 01101000 01110100
~~~
this is very simple !
## DES Data Encryption Standard
### DES is developped by Horst Feistel
Feistel network one round
***************************************************************
* *
* +--------------+ *
* | Input 64 bit | *
* +--------------+ *
* *
* 32bit 32bit *
* +-------+ +-------+ *
* | left | | right | *
* +---+---+ +---+---+ *
* | .----. | *
* | |subkey| | *
* | '-+--' | *
* | v | *
* | +--------+ | *
* XOR o<-+ round |<-+ *
* | |function| | *
* | +--------+ | *
* v v *
* +-------+ +-------+ *
* | left | | right | *
* | crypto| | crypto| *
* +-------+ +-------+ *
* *
* +--------------+ *
* | Output 64bit | *
* +--------------+ *
* *
***************************************************************
$ \forall $ round-function $ . $ this one-step network is symmetric cryptography.
### 3-round Feistel Network
***************************************************************
* *
* 32bit 32bit *
* +-------+ +-------+ *
* | left | | right | *
* +---+---+ +---+---+ *
* | .----. | *
* | |subkey|1 | *
* | '-+--' | *
* | v | *
* | +--------+ | *
* XOR o<-+ round |<-+ *
* | |function| | *
* | +--------+ | *
* v v *
* \_________ / *
* _________\/ *
* / \ *
* v .----. v *
* | |subkey|2 | *
* | '-+--' | *
* | v | *
* | +--------+ | *
* XOR o<-+ round |<-+ *
* | |function| | *
* | +--------+ | *
* v v *
* \_________ / *
* _________\/ *
* / \ *
* v .----. v *
* | |subkey|3 | *
* | '-+--' | *
* | v | *
* | +--------+ | *
* XOR o<-+ round |<-+ *
* | |function| | *
* | +--------+ | *
* v v *
* +-------+ +-------+ *
* | left | | right | *
* | crypto| | crypto| *
* +-------+ +-------+ *
* *
***************************************************************
### Triple-DES
Triple DES is applying 3 times `n-round Feistel Network`
This is now in 2015 is used in some banks.
## AES
AES : Advanced Encrytion Standard
2000 : `Rijndael` is selected as the symmetric cryptography.
finalists of AES selection
| name | applier |
|:---:|:---:|
|RC6|IBM|
|RC6|RSA|
|Rijndael|Daemen,Rijmen|
|Serpent|Anderson, Biham, Knudsen|
|Twofish|Counterpane|
## Rijndael
### SPN structure
******************************************************************************
* data block : 128 bit ( 16 bytes *
* *
* +---+---+---+---+ *
* | | | | <--- 1 byte *
* +---+---+---+---+ *
* | | | | | *
* +---+---+---+---+ *
* | | | | | *
* +---+---+---+---+ *
* | | | | | *
* +---+---+---+---+ *
* *
******************************************************************************
### Encryption
`Subbyte` $ \rightarrow $ `ShiftRows` $ \rightarrow $ `MixColumns` $ \rightarrow $ `AddRoundKey`
******************************************************************************
* *
* *
* +---+---+---+---+ +---+---+---+---+ *
* | | | | | | | | | | *
* +---+---+---+---+ Subbyte() +---+---+---+---+ *
* | | |s12| | -------------> | | |t12| | *
* +---+---+---+---+ map from +---+---+---+---+ *
* | | | | | Subbyte | | | | | *
* +---+---+---+---+ Mappings +---+---+---+---+ *
* | | | | | | | | | | *
* +---+---+---+---+ +---+---+---+---+ *
* *
* *
* *
* *
* *
* +---+---+---+---+ +---+---+---+---+ *
* |s00| | | | |s00| | | | *
* +---+---+---+---+ ShiftRow() +---+---+---+---+ *
* |s10|s11|s12|s13| -------------> |s13|s10|s11|s12| *
* +---+---+---+---+ +---+---+---+---+ *
* |s20| | | | | | |s20| | *
* +---+---+---+---+ +---+---+---+---+ *
* |s30| | | | | | | |s30| *
* +---+---+---+---+ +---+---+---+---+ *
* *
* *
* *
* MixColumns() *
* *
* +---+---+---+---+ +---+---+---+---+ *
* | | |s02| | 4x4 Matrix | | |t02| | *
* +---+---+---+---+ * si-vector +---+---+---+---+ *
* | | |s12| | -------------> | | |t12| | *
* +---+---+---+---+ +---+---+---+---+ *
* | | |s22| | | | |t22| | *
* +---+---+---+---+ +---+---+---+---+ *
* | | |s32| | | | |t32| | *
* +---+---+---+---+ +---+---+---+---+ *
* *
* *
* *
* *
* AddRoundKey() *
* +---+---+---+---+ +---+---+---+---+ *
* | | | | | | | | | | *
* +---+---+---+---+ XOR +---+---+---+---+ *
* | | |s12| | ------->o----> | | |t12| | *
* +---+---+---+---+ ^ +---+---+---+---+ *
* | | | | | | | | | | | *
* +---+---+---+---+ | +---+---+---+---+ *
* | | | | | | | | | | | *
* +---+---+---+---+ | +---+---+---+---+ *
* | *
* | *
* +---+---+---+---+ *
* | | | | | *
* +---+---+---+---+ *
* | | |k12| | *
* +---+---+---+---+ *
* | | | | | *
* +---+---+---+---+ *
* | | | | | *
* +---+---+---+---+ *
* *
* *
******************************************************************************
### Decryption
`AddRoundKey` $ \rightarrow $ `InvMixColumns` $ \rightarrow $ `InvShiftRows` $ \rightarrow $ `InvSubbyte`
### Is this valid ?
This cryptography is mathematically defined .
So if this mathematical function is solved , this encryption no longer will be useful.
But in 2016 , this is still valid .
# Mode
## block and stream
### block
- block cipher : AES, DES ..
- block length : AES 128bit , DES 64bit
### stream
- stream cypher : one-time pad
do not have length !
streaming 1 or 8 or 32 bit encryption
## mode
If plaintext sentence is longer than length of a block,
we apply mode ( the sentence devided into each block by block length).
This application is called `mode`.
### ECB mode
Electric CodeBook mode
***************************************************************
* *
* *
* *
* +-----------+ .-----. +-----------+ *
* block1 | plaintext |-+encrypt+--->| cypertext | *
* +-----------+ '-----' +-----------+ *
* *
* +-----------+ .-----. +-----------+ *
* block2 | plaintext |-+encrypt+--->| cypertext | *
* +-----------+ '-----' +-----------+ *
* *
* +-----------+ .-----. +-----------+ *
* block3 | plaintext |-+encrypt+--->| cypertext | *
* +-----------+ '-----' +-----------+ *
* *
* +-----------+ .-----. +-----------+ *
* block4 | plntxt |-+encrypt+--->| cypertext | *
* +---------^-+ '-----' +-----------+ *
* | *
* padding *
* *
***************************************************************
If someone malicious echange blocks, this can be fatal attack.
### CBC mode
Cipher Block Chaining mode
***************************************************************
* +-----------+ *
* |init vector| *
* +-----+-----+ *
* +---------+ *
* +-----------+ .----. v +-----------+ *
* block1 | plaintext +-+encrpt+-o-->+ cypertext | *
* +-----------+ '----' XOR +-----+-----+ *
* +---------+ *
* +-----------+ .----. v +-----------+ *
* block2 | plaintext +-+encrpt+-o-->+ cypertext | *
* +-----------+ '----' XOR +-----+-----+ *
* +---------+ *
* +-----------+ .----. v +-----------+ *
* block3 | plaintext +-+encrpt+-o-->+ cypertext | *
* +-----------+ '----' XOR +-----+-----+ *
* +---------+ *
* +-----------+ .----. v +-----------+ *
* block4 | plntxt +-+encrpt+-o-->+ cypertext | *
* +---------^-+ '----' XOR +-----------+ *
* | *
* padding *
* *
***************************************************************
#### CTS mode
***************************************************************
* *
* ... ... *
* | *
* +------------------+ *
* +-----------+ v .----. +-----------+ *
* block4 | plaintext +-o+-+encrpt+->+ cyphrtxt4 | *
* +-----------+ '----' +-----+-----+ *
* +------------------' *
* +-----------+ v .----. +----.------+ *
* block5 | plaintext +-o+-+encrpt+->+ E | X | *
* +-----------+ '----' +--+-'----+-+ *
* +----------------------+ +----+ *
* +----+ v +---+ .----. +-----------+ | *
* block6 | P +-o-->+ +-+encrpt+->+ cyphrtxt6 | | *
* +----+XOR +---+ '----' +-----------+ | *
* | X |<-------------------------+ *
* | | *
* +---+ *
* *
***************************************************************
### CFB mode
cypher feedback mode
***************************************************************
* *
* *
* *
* +-----------+ *
* | init vect | *
* .-----. +-----+-----+ *
* +encrypt+<---------' *
* +-----------+ '--+--' +-----------+ *
* block1 | plaintext |-----o------->| cypertext | *
* +-----------+ .-----. +-----+-----+ *
* +encrypt+<---------' *
* +-----------+ '--+--' +-----------+ *
* block2 | plaintext |-----o------->| cypertext | *
* +-----------+ .-----. +-----+-----+ *
* +encrypt+<---------' *
* +-----------+ '--+--' +-----------+ *
* block3 | plaintext |-----o------->| cypertext | *
* +-----------+ .-----. +-----+-----+ *
* +encrypt+<---------' *
* +-----------+ '--+--' +-----------+ *
* block4 | plaintext |-----o------->| cypertext | *
* +-----------+ XOR +-----------+ *
* *
* *
* *
***************************************************************
This is similar with one-time pad encryption.
And the output of encrypt function is called `key stream`.
This `key stream` resembles one-time pad key.
#### replay attack
### OFB mode
Output-FeedBack mode :
feedback the output of encryption for next encryption
***************************************************************
* *
* +---------+ *
* |init vect| *
* +----+----+ *
* v *
* .--+--. *
* |encrypt| *
* '--+--' *
* +-------------------------+ *
* .--v--. +-----------+ v +-----------+ *
* |encrypt| | plntxt 1 |------o------>| cypertext | *
* '--+--' +-----------+ XOR +-----------+ *
* +-------------------------+ *
* .--v--. +-----------+ v +-----------+ *
* |encrypt| | plntxt 2 |------o------>| cypertext | *
* '--+--' +-----------+ XOR +-----------+ *
* +-------------------------+ *
* .--v--. +-----------+ v +-----------+ *
* |encrypt| | plntxt 3 |------o------>| cypertext | *
* '--+--' +-----------+ XOR +-----------+ *
* +-------------------------+ *
* +-----------+ v +-----------+ *
* | plntxt 4 |------o------>| cypertext | *
* +-----------+ XOR +-----------+ *
* *
* *
* *
***************************************************************
### CTR mode
counter mode is very simple.
because,
$$ Encrytion\ Structure = Decryption\ Structure $$
and `concurrent` execution of encryption is possible,
which is not in OFB mode.
********************************************************************
* *
* +-----+ .--+--. *
* |ctr +->|encrypt| *
* +-----+ '--+--' *
* +-------------------------+ *
* +-----+ .--v--. +-----------+ v +-----------+ *
* |ctr+1+->|encrypt| | plntxt 1 |------o------>| cypertext | *
* +-----+ '--+--' +-----------+ XOR +-----------+ *
* +-------------------------+ *
* +-----+ .--v--. +-----------+ v +-----------+ *
* |ctr+2+->|encrypt| | plntxt 2 |------o------>| cypertext | *
* +-----+ '--+--' +-----------+ XOR +-----------+ *
* +-------------------------+ *
* +-----+ .--v--. +-----------+ v +-----------+ *
* |ctr+3+->|encrypt| | plntxt 3 |------o------>| cypertext | *
* +-----+ '--+--' +-----------+ XOR +-----------+ *
* +-------------------------+ *
* +-----------+ v +-----------+ *
* | plntxt 4 |------o------>| cypertext | *
* +-----------+ XOR +-----------+ *
* *
* *
* *
********************************************************************
### conclusion
| name | advantage | disadvantage | - |
|:---:|:---|:---|:---:|
| ECB | simple
quick
conccurent | single key
replay attack | do not use |
| CBC | repeating plaintext not reflect cyphertxt
concurrent(decrypt)
| 1 err -> 2 blocks err
not concurrent(encrypt) | recommended |
| CFB | no need padding
arbitrary decryption | encrypt not conccurent
1bit err -> 1 block & 1bit err
replay attack | - |
| OFB | no padding
the same decrypt structure
1 bit err -> 1 bit err | not concurrent | - |
| CTR | no padding
the same decrypt structure
1 bit err -> 1 bit err
concurrent | - | recommended |
# Public Key cryptography
## key distribution problem (鍵配送問題)
### Question
how to solve key distribution problem ?
### A1. key distribution center
as usual every nodes are distributed his/her key by a center.
### A2. Diffie-Hellman key exchange
see [chapter 11](#chapter11)
### A3. Public Key
dispart key into 2 keys;
- encryption key -- public
- decryption key -- secret
A sends B a message
1. A ping B
2. B generate 2 keys
3. B sends encryption key to A
4. A write and encrypt message and send to B.
5. only B can decrypt the message.
## mathematic basis of mod
discrete log ? (離散対数)
log
$$ 7 ^ \Box = 49 $$
discrete log
$$ 7 ^ \Box mod 13 = 8 $$
the algorithm is not found to search
discrete log quickly ..
## RSA
### RSA Encrypt
$$ (\ CypherText\ ) \ = \ (\ PlainText\ ) ^ { E } \ \mod N $$
### RSA Decrypt
$$ (\ PlainText\ ) \ = \ (\ CypherText\ ) ^ { D } \ \mod N $$
here ,
- public key : E and N
- private key : D and N
### how to make E,D,N
$ p,q $ : prime number
$$ N = p \times q $$
$$ L = lcm (p-1,q-1) $$
$$ 1 < E < L $$
$$ gcd (E,L) = 1 $$
$$ 1 < D < L $$
$$ E \times D \ mod \ L \ = \ 1 $$
### attacks
- brute force attack
- E , p and q creates secret key ,so 素因数分解 N
- man in the middle attack (MITM)
how to stop MITM ?
- [certificate(証明書)](chpter10)
# hybrid cryptosystem
hybrid of `pulic key crypto` and `symmetric crypto`
- `message` is encrypted with `symmetric crypto`
- `session key` used by `symmetric crypto` is pseudo-random generated.
- `session key` is encrypted eith `public key`
## encrypttion
****************************************************************************************************
* *
* *
* +-----------+ *
* | message | *
* | | *
* +-----+-----+ *
* | *
* .-------------. | *
* |pseudo rand gen| | *
* '------+------' v *
* +---v---+ .---+---. *
* |session+----->|symmetric| *
* | key | | encrypt | *
* +---+---+ '---+---' *
* v | *
* +---------+ .---+---. | *
* |recievers+----->+ pub-key | | *
* | pub key | | encrypt | | *
* +---------+ '---+---' | *
* v v *
* +---+---+ +-----+-----+ *
* |pbk-cyp| |sym-cypherd| *
* | key | | message | *
* +---+---+ +-----+-----+ *
* | .----. | *
* +--->+ bind +<--+ *
* '--+-' *
* v *
* +-------+-+---------+ *
* |pbk-cyp|sym-cypherd| *
* | key | message | *
* +-------+-----------+ *
* *
* *
****************************************************************************************************
## decryption
****************************************************************************************************
* *
* *
* +-------+-----------+ *
* |pbk-cyp|sym-cypherd| *
* | key | message | *
* +-------+-+---------+ *
* v *
* .--+-. *
* +----+devide+---+ *
* v '----' v *
* +---+---+ +-----+-----+ *
* |pbk-cyp| |sym-cypherd| *
* | key | | message | *
* +---+---+ +-----+-----+ *
* v | *
* +---------+ .---+---. | *
* |private +----->+ pub-key | | *
* | key| | decrypt | | *
* +---------+ '---+---' | *
* v v *
* +---+---+ .---+---. *
* |session+----->|symmetric| *
* | key | | decrypt | *
* +-------+ '---+---' *
* | *
* | *
* v *
* +-----------+ *
* | message | *
* | | *
* +-----+-----+ *
* *
* *
****************************************************************************************************
# Authenticate
integrity :
- the quality of being honest and having strong moral principles
- the state of being whole and not divided
# one-way hash function
****************************************************************************************************
* *
* *
* *
* *
* +-----------------------------------+ *
* | | *
* | | *
* | Big mass of data | *
* | or | *
* | small data | *
* | | *
* | | *
* +-----------------+-----------------+ *
* v *
* .-----------+-----------. *
* | one way hash function | e.g. SHA256 *
* '-----------+-----------' *
* v *
* +------+------+ *
* | fingerprint | *
* +-------------+ *
* *
* *
* *
****************************************************************************************************
software's fingerprint proves it is the original one and not changed by someone.
## e.g.
| function | birth | bit | security |
|:---:|:---:|:---:|:--- |
| MD4 | Rivest 1990 | 128 | Dobbertin find how to find corrision of fingerprint |
| MD5 | Rivest 1991 | 128 | not safe , 強衝突耐性なし |
| SHA1 | NIST 1993 | 160 | 2014? found corrision finding way of fingerprint |
| RIPEMD | EU Ripe | - | not safe, 強衝突耐性なし(2004) |
| RIPEMD-160 | Dobbertin.. 1996 | 160 | used in bitcoin |
| SHA3 | | | |
## KECCAK
- Picture liscence are from [http://sponge.noekeon.org](http://sponge.noekeon.org)
- Picture liscence are from [http://keccak.noekeon.org](http://keccak.noekeon.org)
- [Keccak tools](https://github.com/gvanas/KeccakTools) are open source tools by Gilles Van Assche.
### Sponge
![sponge structure](/image/keccak/Sponge-150.png width="600")
b : bit width
$ b := r + c $
### Duplex
![duplex structure](/image/keccak/Duplex-150.png width="600")
### function
$$ f = f _ \iota \circ f _ \chi \circ f _ \pi \circ f _ \pi \circ f _ \theta $$
bit width $ b $ : $ b \in \{ 25,50,100,200,400,800,1600 \} $
![f pieses of states](/image/keccak/Keccak-f-PiecesOfState.png width="600")
here,
- $ x = y = 5 $
- $ z \in \{ 1,2,4,8,16,32,64 \} $
so,
#### $ \theta $ step
![f_theta](/image/keccak/Keccak-f-Theta.png width="300")
#### $ \rho $ step
![f_rho](/image/keccak/Keccak-f-Rho.png width="700")
#### $ \pi $ step
![f_pi ](/image/keccak/Keccak-f-Pi.png width="500")
#### $ \chi $ step
![f_chi](/image/keccak/Keccak-f-Chi.png width="200")
#### $ \iota $ step
see [next](#toc8.2.4)
### Pseudo-code description
We first start with the description of Keccak-f in the pseudo-code below. The number of rounds nr depends on the permutation width, and is given by nr = 12+2l, where 2l = w. This gives 24 rounds for Keccak-f[1600].
~~~
Keccak-f[b](A) {
forall i in 0…nr-1
A = Round[b](A, RC[i])
return A
}
Round[b](A,RC) {
θ step
C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4], forall x in 0…4
D[x] = C[x-1] xor rot(C[x+1],1), forall x in 0…4
A[x,y] = A[x,y] xor D[x], forall (x,y) in (0…4,0…4)
ρ and π steps
B[y,2*x+3*y] = rot(A[x,y], r[x,y]), forall (x,y) in (0…4,0…4)
χ step
A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), forall (x,y) in (0…4,0…4)
ι step
A[0,0] = A[0,0] xor RC
return A
}
~~~
In the pseudo-code above, the following conventions are in use. All the operations on the indices are done modulo 5. A denotes the complete permutation state array, and A[x,y] denotes a particular lane in that state. B[x,y], C[x], D[x] are intermediate variables. The constants r[x,y] are the rotation offsets (see Table 2), while RC[i] are the round constants (see Table 1). rot(W,r) is the usual bitwise cyclic shift operation, moving bit at position i into position i+r (modulo the lane size).
Then, we present the pseudo-code for the Keccak[r,c] sponge function, with parameters capacity c and bitrate r. The description below is restricted to the case of messages that span a whole number of bytes. For messages with a number of bits not dividable by 8, we refer to the specifications [1] for more details. Also, we assume for simplicity that r is a multiple of the lane size; this is the case for the SHA-3 candidate parameters in [2].
~~~
Keccak[r,c](M) {
Initialization and padding
S[x,y] = 0, forall (x,y) in (0…4,0…4)
P = M || 0x01 || 0x00 || … || 0x00
P = P xor (0x00 || … || 0x00 || 0x80)
Absorbing phase
forall block Pi in P
S[x,y] = S[x,y] xor Pi[x+5*y], forall (x,y) such that x+5*y < r/w
S = Keccak-f[r+c](S)
Squeezing phase
Z = empty string
while output is requested
Z = Z || S[x,y], forall (x,y) such that x+5*y < r/w
S = Keccak-f[r+c](S)
return Z
}
~~~
In the pseudo-code above, S denotes the state as an array of lanes. The padded message P is organised as an array of blocks Pi, themselves organized as arrays of lanes. The || operator denotes the usual byte string concatenation.
### Round constants
The round constants RC[i] are given in the table below for the maximum lane size 64. For smaller sizes, they are simply truncated. The formula can be found in [1].
~~~
RC[ 0] 0x0000000000000001 RC[12] 0x000000008000808B
RC[ 1] 0x0000000000008082 RC[13] 0x800000000000008B
RC[ 2] 0x800000000000808A RC[14] 0x8000000000008089
RC[ 3] 0x8000000080008000 RC[15] 0x8000000000008003
RC[ 4] 0x000000000000808B RC[16] 0x8000000000008002
RC[ 5] 0x0000000080000001 RC[17] 0x8000000000000080
RC[ 6] 0x8000000080008081 RC[18] 0x000000000000800A
RC[ 7] 0x8000000000008009 RC[19] 0x800000008000000A
RC[ 8] 0x000000000000008A RC[20] 0x8000000080008081
RC[ 9] 0x0000000000000088 RC[21] 0x8000000000008080
RC[10] 0x0000000080008009 RC[22] 0x0000000080000001
RC[11] 0x000000008000000A RC[23] 0x8000000080008008
here, 1 nibble is 4 bit; 4 bit/nibble x 16 nibble = 64 bit
~~~
Table 1: The round constants RC[i]
### Rotation offsets
The rotation offsets r[x,y] are given in the table below. The formula can be found in [1].
~~~
x = 3 x = 4 x = 0 x = 1 x = 2
y = 2 25 39 3 10 43
y = 1 55 20 36 44 6
y = 0 28 27 0 1 62
y = 4 56 14 18 2 61
y = 3 21 8 41 45 15
~~~
Table 2: the rotation offsets
## attacks
- collision : two different data generates the same fingerprint
### preimage attack
- preimage attack : find the data with numerious calculation
- second preimage attack : find the collision data with numerious calculation
### collision attack
1. Maroly finds the two data whose fingerprint is the same.
2. Maroly intruoduce Alice one of them and make Alice caluculate the fingerprint.
3. Maroly can exchange the two data without Alice's eye.
this is also called "birthday attack"
Q. How many people can be up to the probability of 1/2 that two of their birthday is the same.
A.
$$ 1 - \frac{365 \times 364 \times ... \times (365 - N + 1)}{ 365 ^ N } \ge \frac{1}{2} $$
$$\therefore N \ge 23 $$
But,this cannot find なりすまし .
# message authentication code
message authentication code (MAC) : one-way hash function depending on `shared key`.
*********************************************************************************
* *
* +-------------+ +------+ +-------------+ *
* | | |shared| | | *
* | message | | key | | message | *
* | | +----+-+ | | *
* +------+------+ \ +------+------+ *
* v v v *
* .-----------+-----------. .-------------+-------------. *
* | one way hash function | | message authentication code | *
* '-----------+-----------' '-------------+-------------' *
* v v *
* +-----'-----+ +-----'-----+ *
* |fingerprint| | MAC value | *
* +-----------+ +-----------+ *
* *
*********************************************************************************
## How to use
*********************************************************************************
* +--------------------------------+ +--------------------------------+ *
* | Bank Alice | | Bank Bob | *
* | +-------------+ | | +-------------+ | *
* | | | | | | | | *
* | | message +------------------------>+ message | | *
* | | "send money"| | | | | | *
* | +------+------+ | | +------+------+ | *
* | | | | | | *
* | v | | v | *
* | +------+ .-------+-------. | | +------+ .-------+-------. | *
* | |shared+--->+ message code || | |shared+--->+ message code || *
* | | key | | authentication || | | key | | authentication || *
* | +------+ '-------+-------' | | +------+ '-------+-------' | *
* | | | | | | *
* | v | | v | *
* | +-----'-----+ | | +-----------+ +-----'-----+ | *
* | | MAC value +----------->+ MAC value | | MAC value | | *
* | +-----------+ | | +-----+-----+ +-----.-----+ | *
* | | | | .------. | | *
* | | | +->+ compare+<-+ | *
* | | | '------' | *
* +--------------------------------+ +--------------------------------+ *
*********************************************************************************
There is still key distribution problem.
## use case of Message Authentication Code
### SWIFT
Society for Worldwide Interbank Financial Telecommunication
- founded in 1973
- 213 countries in 2013
- use Public key crypto for shared key
### IPsec
Internet Protocol security
-use MAC
### SSL/TLS
-use MAC
## Inplementation of MAC
AE, AEAD
- AE : authenticated Encryption
- AEAD : Authenticated Encryption with Associated Data
### GCM, GMAC
### HMAC
****************************************************************************************
* *
* *
* +---------------+ *
* | | *
* | message | *
* | | *
* +-------+-------+ *
* | *
* +--------------------------------------------|--------------+ *
* +-----+ | +-----+-------+ | | *
* | key +------>+ key | 0 pad | | | *
* +-----+ | +--+--+-------+ | | *
* | | | | *
* | | +-------------+ | | *
* | | | ipad | | | *
* | | +------+------+ | | *
* | | v .---+--. | *
* | +------------>o------------------>+ bind | | *
* | | XOR '---+--' | *
* | | v | *
* | | +-------------+ .-----------+-----------. | *
* | | | opad | | one way hash function | | *
* | | +------+------+ '-----------+-----------' | *
* | | | v | *
* | | v .---+--. | *
* | +------------>o------------------>+ bind | | *
* | XOR '---+--' | *
* | v | *
* | .-----------+-----------. | *
* | | one way hash function | | *
* | HMAC '-----------+-----------' | *
* +--------------------------------------------|--------------+ *
* | *
* v *
* +-----+-----+ *
* | MAC VALUE | *
* +-----------+ *
* *
* *
****************************************************************************************
- ipad = repeat `00110110` until block length
- opad = repeat `01011100` until block length
~~~
hash(opadkey || hash(ipadkey || message))
where,
ipadkey = key XOR ipad
opadkey = key XOR opad
~~~
here we can name inner-pad and outer-pad.
## problems
- With MAC, Bob cannot prove to third party (Chris) that Alice sends this message to Chris.
- `repudiation` proof : Alice said, " I do not send such a message ". Anyone cannot prove this.
# Digital Signature
## お母さんヤギの認証
オオカミ :「お母さんですよ、このドアを開けておくれ」
子ヤギ : 「お母さんは白い手だよ」
オオカミは手を白く塗った。
オオカミ : 「お母さんですよ。鍵を開けておくれ」
子ヤギは白い手を見て扉を開けた。
~~~
「お母さんヤギにしかつくれない情報」があれば「なりすまし」は防ぐことができる
~~~
## Digital Signature
### Digital Signature has 2 processes
- generate signature
- verify sugnature
| \ | private key | public key |
|:---:|:---|:---|
| PBK cryptography | reciever's decode | sender's encode |
| Digital Signature | sender's generate signature | reciever's verify signature |
| who own the key ? | individual | those all who needs the key |
### 2 ways of generate Signature
- generate signature on message (just remove `1 way hash function`s from below graph )
- generate signature on hashed message
******************************************************************************************
* *
* *
* +-----------------------+ +------------------------------------+ *
* | sender Alice | | receiver Bob | *
* | +---------+ | | +---------+ | *
* | | message +----------------------------->+ message | | *
* | +----+----+ | | +----+----+ | *
* | v | | v | *
* | .---+---. | | .---+---. | *
* | |1way hash| | | |1way hash| | *
* | '---+---' | | '---+---' | *
* | v | | v | *
* | +---------+ | | +----+----+ | *
* | |hashd val| | | |hashd val| | *
* | +----+----+ | | +----+----+ | *
* | +-------+ v | | | | *
* | | Alice | .--+--. | | | | *
* | |private+->+encrypt| | | | | *
* | | key | '--+--' | | | | *
* | +-------+ v | | | | *
* | +---------+ | | +---------+ | | *
* | |signature+------------------>+signature| | | *
* | +---------+ | | +----+----+ | | *
* | | | +-------+ v | | *
* +-----------------------+ | | Alice | .--+--. | | *
* | |public +->+decrypt| | | *
* | | key | '--+--' | | *
* | +-------+ v | | *
* | +----+----+ | | *
* | |hashd val| | | *
* | +----+----+ | | *
* | v v | *
* | .-+----------+-. | *
* | | compare | | *
* | '--------------' | *
* | | *
* +------------------------------------+ *
******************************************************************************************
## RSA Digital Signature
### generate signature
$$ (\ Signature\ ) \ = \ (\ Message\ ) ^ { D } \ \mod N $$
### verify signature
$$ (\ Message\ ) \ = \ (\ Signature\ ) ^ { E } \ \mod N $$
here ,
- public key : E and N
- private key : D and N
### how to make E,D,N
$ p,q $ : prime number
$$ N = p \times q $$
$$ L = lcm (p-1,q-1) $$
$$ 1 < E < L $$
$$ gcd (E,L) = 1 $$
$$ 1 < D < L $$
$$ E \times D \ mod \ L \ = \ 1 $$
## other Signature
### ElGamal
- it uses tha fact that it is difficult to solve (discrete log mod N).
### DSA
- developped DlGamal by NIST(National Institute of Standards and Technology)
### ECDSA
* Elliptic Curve Digital Signature
### Rabin'\''s way
* difficult to solve (square-root mod N)
## Attacks
* if you are not good at how digital signature works you can be attacked.
* man in the middle attack can be possible if there is no way for receiver to know real PBK.
# Certificate
the PBK you have is real one ?
## Certificate
- PKC (public key certificate) : like your Driver's Licence / PassPort
- CA (certification authority) : the center who publish certificate
- e.g. ベリサイン
- Trent : we call reliable CA "trent"
********************************************************************
* *
* *
* *
* +--------------+ *
* | C A | *
* .----------------. | Trent | *
* | Certificate | +--+--------+--+ *
* | .--------------. | / ^ *
* ||Bob's Public Key|| / \ .--------------. *
* | +--------------+ | / \ |Bob's Public Key| *
* ||Tre's DigitalSig|| / \ '--------------' *
* | '--------------' | / \ *
* '----------------' v \ *
* +--------------+ +---+------------+ *
* |message sender+------------->|message reciever| *
* | Alice | | Bob | *
* +--------------+ +----------------+ *
* *
* *
* *
* *
********************************************************************
1. Bob make key-pair
2. Bob register his PubKey at Trent
3. Trent make a certificate encrypted with Trent's Private Key
4. Alice get the certificate
5. Alice decrypt it with Trent's PubKey and check it is valid.
6. Alice send message encrypted with Bob's PubKey
7. Bob decrypts Alice's message with his own private key
This system garantees that Bob's PubKey is truely Bob's.
ボブの鍵で暗号化するとボブ本人にしかそれを解読することはできないのでセキュリティが保たれる#
## Let's make a Certificate !
### Generate Key & Install on Symantec
we can make a 25-days-certificate with an email-address on [Symantec HomePage](http://www.symantec.com/digital-id/)
there,
1. generate key
2. install certificate (download SelfService.action.p7s)
### show the contents of the certificate
use `gpgsm` command from `GnuPG` package
~~~
$ gpgsm --import SelfService.action.p7s // import certificate
$ gpgsm --dump-cert // dump the imported certificate
~~~
### Standardization for certificate
`X.509` : standardization for certificate defined in ISO or ITU(International Telecommunication Union)
| | |
|:---|:---|
| Sirial Number| S/N : 24... |
| Issuer | Issuer: CN=Symantec Class 1 Individual Subscriber CA - G4,... |
| Owner of PBK | Subject: ...aka: |
| fingerprint by SHA1 | sha1_fpr: 39:28: ... :A0:E1 |
| fingerprint by MD5 | md5_fpr: 95:2B: ... :39:FD |
| ID | certid: 2127F3D48..21D34.121A78F1...B2 |
| valid time | notBefore: 2015-06-12 00:00:00 |
| valid time | notAfter: 2015-07-07 23:59:59 |
| hash algorithm | hashAlgo: 1.2.840.113549.1.1.5 (sha1WithRSAEncryption) |
| key type | keyType: 2048 bit RSA |
| key ID | subjKeyId: EAD8...C740 |
| Purpose of Key Usage | KeyUsage: digitalSignature keyEncipherment |
## PKI
### PKI
PKI(public-key infrastructure)
e.g.
* PKCS(Public-Key Cryptography Standards) $ \in $ PKI
* RFC(Requests for Comments) $ \in $ PKI
* X.509 $ \in $ PKI
see [http://www.ipa.go.jp/security/pki/](http://www.ipa.go.jp/security/pki/)
### Components of PKI
PKI consists of
* entity (user)
* certification authority
* repository -- this stores certificate
#### entity
entity who register PBKey does
* generate key pair
* register PBKey on CA -- RFC2986(PKCS #10: Certification Request Syntax Specification)
* receive certificate from CA
* if needed ask CA to invalidate the PBKey
* decrypt recieved message
* digital signnature on messages
entity who use the PBKey does
* encrypt messages and send it
* varify digital signature
#### CA
what CA does
* generate key pair (in case entity do not generate)
* varify entity when the entity register PBKey -- RFC7292(PKCS #12: Personal Informaion Exchange Syntax v1.7)
* make and issue certificate -- CPS(certification practice statement)
* delete(revocate) certificate
CA has CRL(sertificate revocation list); the list of digital signature with deleted certificate's Sirial Number
so,
~~~
entity must Download CRL and check the certificate is valid
~~~
#### Repository
証明書における「電話における電話帳のようなもの」
Sometimes, we call it "certificate Directory"
### 階層化された certificate
~~~
root CA
|
Hokkaido CA
|
Sapporo CA
~~~
### GPKI
government also defines PKI
http://www.gpki.go.jp/ is defined by Japan Government
## Attacks against certificates
###
### registering similar name
register `BOB` for `Bob`
### theif private key of CA
CA must broadcast on CRL if private key is stolen.
### make himself CA (bad CA)
### CRL 1
it takes time to issue CRL and entity's reloading the new CRL
so,
if PBkey go fall invaid,
* tell that to the CA ASAP (Bob)
* CA issues CRL ASAP (Trent)
* redownload CRL always (Alice)
### CRL 2
it takes time to issue CRL and entity's reloading the new CRL
Here, Bob is bad person
1. Bob really send message to Alice , "give $100,000 to this address."
2. and Later Bob said to Alice , "the message is not mine."
this makes Bob did not receive money publicly.
### superfish
2015 superfish(virus) was pre-installed on Lenovo
### _
## ID Based Encryption; IBE
different approach from CA
# Key
## keys
### common key encryption <--> public key encription
### session key
session key : one-time key for network communication
e.g. SSL/TLS
### CEK and KEK
* CEK : contents encrypting key
* KEK : key encrypting key
## manage keys
### make key from pseudo-rand only
Do not do because there is no "impossibility for expectations"
### make key from password or passphrase
this is called "PBE(password based encryption)"
add ` salt (random number) ` to avoid dictionary attack
### key distribution
* key distribution center
* public key
* Diffie-Hellman Key Exchange
### key update
the algorithm is like this
~~~
key = hash(key)
~~~
### key store
## Diffie Hellman Key Exchange
******************************************************************
* *
* *
* +-------+ *
* | G,P | *
* |(open) | *
* +-------+ *
* / \ *
* / \ *
* +--------+ / | \ +--------+ *
* | A | v v | B | *
* | secret +---->o | o<----+ secret | *
* +---+----+ | | +---+----+ *
* | v | v | *
* | +-----+----+ +----+-----+ | *
* | |G**A mod P| | |G**B mod P| | *
* | | (open) | | (open) | | *
* | +----------+ | +----------+ | *
* v \ / | *
* o<----------------\-+ v *
* | '---------------->o *
* | | *
* v | v *
* +----+--------+ +-------+-----+ *
* |G**(AB) mod P| | |G**(AB) mod P| *
* | common key | | common key | *
* +-------------+ | +-------------+ *
* *
* *
******************************************************************
now think
mod P
where P = 13
then
G = 2,6,7,11 (Generating element)
because otherwise G cannot generate all number like below.
| G\A | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|:---:|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 4 | 8 | 3 | 6 | 12 | 11 | 9 | 5 | 10 | 7 | 1 |
| 3 | 3 | 9 | 1 | 3 | 9 | 1 | 3 | 9 | 1 | 3 | 9 | 1 |
| ... |||||||||||||
| 12 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 | 12 | 1 |
### Elliptic Curve Diffie-Hellman Key Exchange
* The Diffie-Hellman uses : Discrete Logarithm problem
* EC Diffie-Hellman : Elliptic Curve
## PBE (password based encryption)
* RFC2898(PKCS #5)
* RFC7292(PKCS #12)
PBE do not require keeping KEK(key encrypting keys)
This keeps keys safe from dictionary attack .
PBE encryption
******************************************************************************
* *
* .-----. +---------+ *
* | Alice | | message | *
* '--+--' +----+----+ *
* | | *
* | | *
* --------------------|-------+---------------------+---------|--------- *
* | | | | *
* .------------. | | | *
* |pseudoRand gen| | | | *
* '------+-----' | | | *
* v v | | *
* +------+ +----+---+ | | *
* | salt | |password| .------------. | | *
* +---+--+ +----+---+ | |pseudoRand gen| | *
* | | '------+-----' | v *
* +-----+-----+ | v .----+----. *
* v +--+--+ | | symmetric | *
* .--------+--------. | | CEK +---------->+ encryption| *
* |1 way hash function| +--+--+ | '----+----' *
* '--------+--------' | v | *
* v .----+----. | | *
* +--+--+ | | symmetric | | *
* | KEK +-------------->+ encryption| | | *
* +-----+ | '----+----' | *
* v | | *
* | +-------+-------+ | *
* | encrypted CEK | | | *
* | +---------------+ | *
* | | | *
* ---------------------------+---------------------+---------|--------- *
* | *
* v *
* -------------------------+ +---------+-------+ *
* safe space | |encrypted message| *
* +------+---------------+ | +-----------------+ *
* | salt | encrypted CEK | | *
* +------+---------------+ | *
* | *
******************************************************************************
PBE decryption
******************************************************************************
* *
* .-----. +---------+ *
* | Alice | | message | *
* '--+--' +----+----+ *
* | ^ *
* | | *
* --------------------|-------+---------------------+---------|--------- *
* | | | | *
* | | | *
* | | | *
* | | | *
* v | | *
* +------+ +----+---+ | | *
* | salt | |password| | | *
* +---+--+ +----+---+ | | *
* | | | | *
* +-----+-----+ | .----+----. *
* v +--+--+ | | symmetric | *
* .--------+--------. | | CEK +---------->+ decryption| *
* |1 way hash function| +--+--+ | '----+----' *
* '--------+--------' | ^ ^ *
* v .----+----. | | *
* +--+--+ | | symmetric | | *
* | KEK +-------------->+ decryption| | | *
* +-----+ | '----+----' | *
* ^ | | *
* | +-------+-------+ | *
* | encrypted CEK | | | *
* | +---------------+ | *
* | | | *
* ---------------------------+---------------------+---------|--------- *
* | *
* | *
* -------------------------+ +---------+-------+ *
* safe space | |encrypted message| *
* +------+---------------+ | +-----------------+ *
* | salt | encrypted CEK | | *
* +------+---------------+ | *
* | *
******************************************************************************
# Pseudo Random Number
## what Pseudo Random Number is used for ?
* generate keys
* generate key-pairs
* generate init-vector
* generate nonce
* generate salt
## propertiy of Random Number
* randomness
* unpredictability
* 再現不可能性 irreproduciblity : 再現しようとするなら、同じ数列を保存しておくしか道はない
| --- | randomness | unpredictability | 再現不可能性 |
|:---:|:---:|:---:|:---:|
| weak | ◯ | x | x |
| strong | ◯ | ◯ | x |
| random | ◯ | ◯ | ◯ |
## pseudo random generator
### random generator
Intel's new CPU has "Digital Random Number Generator (DRNG)"
This use heat noise as entolopy source , generating random number.
[DRNG software inplementaion guide](https//software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide)
There are 2 operations
* RDSEED : the return value can be used as a seed
* RDRAND : generates deterministic pseudo random sequence
### Pseudo Random Generator
******************************************************************************
* +-------+ *
* | seed | *
* +---+---+ *
* | *
* .-------v-------. *
* | +------+------+ | +------------------------+ *
* | | inner state | +--------->+ pseudo random sequence | *
* | +-------------+ | +------------------------+ *
* | pseudo random | *
* | Generator | *
* '---------------' *
* *
* *
******************************************************************************
## concrete pseudo random generator
### linear confruential method
first_pseudo_random_number R_0
$ R_0 $ = ( A * seed + C ) mod M
$ R_1 $ = ( A * $ R_0 $ + C ) mod M
...
### Using one way hash function
$ R_0 $ = SHA256(seed)
$ R_1 $ = SHA256(seed + 1)
...
### Using encryption
seed := counter ++ key
$ R_0 $ = encrypt( counter )
$ R_1 $ = encrypt( counter + 1 )
...
### ANSI X9.17
****************************************************************
* *
* *
* +------+ *
* | seed | *
* +------+ *
* /\ *
* .-------------' '--------. *
* | | *
* *
* +----------+ +-----+ *
* |init | | key | *
* |innerstate| | | *
* +----+-----+ '--+--' *
* | +--------+---+ *
* | | | | *
* | | | | *
* v | | v *
* +----+-----+ | XOR .--+--. +------+ *
* |innerstate+--------->o->+encrypt+--+-->| Rand | *
* +-+--------+ | ^ '-----' | +------+ *
* ^ | | | | *
* | +------+ | | | | *
* | | time | | | | | *
* | +--+---+ v | | | *
* | | .--+--. | | | *
* | +->+encrypt+-+------------>o XOR *
* | '-----' | | *
* | v | *
* | .--+--. | *
* +------------------+encrypt+<-----+ *
* '-----' *
* *
* *
* *
* *
* *
* *
* *
* *
****************************************************************
* ANSI X9.17 use triple DES for encryption (?not clear
* ANSI X9.31 use AES for encryption (?not clear
### new random generator by google
# PGP
## PGP
### what is it ?
* started by Philip Zimmermann in 1990
* PGP : pretty good privacy
* OpenPGP : free software
* GnuPG : GNU PG which is created based on OpenPGP
### OpenPGP
defined in
* RFC1991 : support message (1996)
* RFC2440
* RFC4880 : support RSA, DSA (2007)
* RFC5581
* RFC6637 : support ECDSA (2012)
balance of crypto strongness
|ECDSA| ECC | RSA | hash|symmetric|
|:---:|:---:|:---:|:---:|:---:|
|P256 |256 |3072 |256 |128 |
|P384 |384 |7680 |384 |192 |
|P521 |521 |15360|512 |256 |
### GPG
* stable (version 2.0.*)
* modern (version 2.1.*)
* classic (version 1.4.*)
### function of PGP
* symmetric encryption
* public key encryption : RSAR, ElGamal
* digital signature : RSA, DSA, ECDSA, EdDSA, ..
* one way hash funstion : SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, RIPEMD-160, .. , MD5(no recommend)
* certificate : X509, including "revocation certificate"
* compression : zip zlib bzip2
* text data : ASCII_radix-64(:: binary -> text) , base64(:: binary -> text)
* devide and combine large file
* manage " key ring "
## key-pair-gen
install gpg and type :
~~~
$ gpg2 --full-gen-key
~~~
if you make PBK with "A57FF192" (Private key)
~~~
$ gpg2 --export --armor A57FF192
~~~
### PGP encryption
****************************************************************************
* *
* +-------+ *
* |message| *
* +---+---+ *
* | *
* | *
* v *
* .------. .----+----. *
* | Rand() | | compress | *
* '---+--' '----+----' *
* v v *
* +-----+-----+ .--+--. *
* |session key+----->+encrypt| symmetric encryption *
* +-----+-----+ '--+--' *
* v v *
* +--------------+ .--+--. +----+----+ *
* |receiver's PBK+->+encrypt| | message"| *
* +--------------+ '--+--' +----+----+ *
* v | *
* +--------+---------+ | *
* |encrpt session key| | *
* +--------+---------+ | *
* v v *
* .-+----------------+-. *
* | bind | *
* '---------+----------' *
* v *
* .-------+------. *
* | binary -> text | *
* '-------+------' *
* | *
* | *
* v *
* +-------+------+ *
* | sending data | *
* +--------------+ *
* *
****************************************************************************
### PGP decryption
***********************************************************************************************
* *
* +---------+ +--------------+ *
* |Reciever | |receiving data| *
* +----+----+ +-------+------+ *
* | | *
* v | *
* +-----+-----+ | *
* |pass phrase| | *
* +-----+-----+ | *
* v v *
* .--+--. +----+ .-------+------. *
* | bind +<--+salt| | binary -> text | *
* '--+--' +----+ '-------+------' *
* v v *
* .-----+-----. +--------------+ .---------+----------. *
* |1way hash fun| |encryp privKey| | devide | *
* '-----+-----' +-----+--------+ '-+----------------+-' *
* v v v v *
* +----+----+ .-----+-----. +--------+---------+ +----+----+ *
* |Key 4 sym+->+ sym decrypt | |encrpt session key| | message"| *
* +---------+ '-----+-----' +--------+---------+ +----+----+ *
* v v | *
* +-----+-----+ .--+--. | *
* |private key+--------->+decrypt| | *
* +-----------+ '--+--' | *
* v v *
* +-----+-----+ .--+--. *
* |session key+----->+decrypt| symmetric decryption *
* +-----------+ '--+--' *
* v *
* .----+----. *
* | compress | *
* '----+----' *
* v *
* +---+---+ *
* |message| *
* +-------+ *
* *
***********************************************************************************************
## PGP Digital Signature
### generate PGP Digital Signature
***********************************************************************************************
* *
* +---------+ +---------+ *
* | Sender | | message | *
* +----+----+ +----+----+ *
* | | *
* v | *
* +-----+-----+ | *
* |pass phrase| | *
* +-----+-----+ | *
* v | *
* .--+--. +----+ | *
* | bind +<--+salt| +----------------+ *
* '--+--' +----+ | | *
* v v | *
* .-----+-----. +--------------+ .-----+------. | *
* |1way hash fun| |encryp privKey| |1 way hash fun| | *
* '-----+-----' +-----+--------+ '-----+------' | *
* v v v | *
* +----+----+ .-----+-----. +------+-------+ | *
* |Key 4 sym+->+ sym decrypt | | hashed value | | *
* +---------+ '-----+-----' +------+-------+ | *
* v v | *
* +-----+-----+ .-----+-----. | *
* |private key+------>+ Digital Sig | | *
* +-----------+ '-----+-----' | *
* v | *
* +-----+-----+ | *
* |Signed Hash+ | *
* +-----+-----+ | *
* v v *
* .-+----------------+-. *
* | bind | *
* '-+-------+--------+-' *
* v *
* .------------. .----+----. *
* |pseudoRand gen| | compress | *
* '-----+------' '----+----' *
* v v *
* +-----+------+ .---+---. *
* |sesseion key+------>+ encrypt | symmetric encryption *
* +-----+------+ '---+---' *
* v | *
* .----+----. | *
* |PBK encrypt| | *
* '----+----' | *
* v | *
* +---------+---------+ +-------+-------+ *
* |cypherd session key| |cypherd Sig&Msg| *
* +---------+---------+ +-------+-------+ *
* v v *
* .---+-------------------+---. *
* | bind | *
* '-------------+-------------' *
* v *
* .-------+------. *
* | binary -> text | *
* '-------+------' *
* v *
* +-------+------+ *
* | sending data | *
* +--------------+ *
* *
***********************************************************************************************
## web of trust
PGP does not use CA (Certification Authority
### Owner Trust Value
* Ultimately trusted 秘密鍵を持った本人が該当
* Fully trusted
* Marginally trusted
* Never trust this key
* Not enough information 未知
* No ownertrust assigned 未設定
# SSL / TLS
## SSL
SSL : secure socket layer
TLS : Transpot Layer Security
e.g.
we use credit Card on the web
with HTML on SSL/TLS
we send mail
with SMTP on SSL/TLS
we receive mail
with POP3 on SSL/TLS
******************************************************
* *
* *
* *
* +----------+ +------------------+ *
* | browser | | mail application | *
* +----------+ +---------+--------+ *
* | HTML | | SMTP | POP3 | *
* +----------+----+---------+--------+ *
* | SSL / TLS | *
* +----------------------------------+ *
* *
* *
* *
******************************************************
### cyper suite
cypher suite : recommended set of crypto technology used by SSH/TLS
e.g.
* (RSA, SDES)
* (DSS, AES)
## telecommunication with SSL/TLS
### TLS protocol
*******************************************************************************
* *
* TLS Protocol *
* *
* +-----------+ +----------+ +----------+ +-----------+ *
* TLS Handshake | Handshake | | Change | | Alert | |Application| *
* Protocol | | |CypherSpec| | | | protocol | *
* '-----------+ +----------+ +----------+ +-----------' *
* *
* TLS Record .---------------------------------------------------. *
* Protocol | Record Protocol | *
* '---------------------------------------------------+ *
* *
* .---------------------------------------------------. *
* TCP protocol | TCP | *
* '---------------------------------------------------+ *
* *
* *
*******************************************************************************
#### TLS Record Protocol
The lower layer established below TLS Handshake Protocol.
#### TLS Handshake protocol
The Handshake protocols of the TLS/SSL protocol are responsible for establishing or resuming secure sessions.
##### Handshake
This sub-protocol is used to negotiate session information between the client and the server.
**********************************************************************************
* *
* *
* *
* *
* +----------+ +----------+ *
* | Client | | Server | *
* +----+-----+ +-----+----+ *
* | | *
* | ClientHello | *
* +-------------------------------------------------------->| *
* | * version No | *
* | * time | *
* | * client random | *
* | * session ID | *
* | * list of cypher suite | *
* | * list of compression way | *
* | | *
* | | *
* | ServerHello | *
* +<--------------------------------------------------------+ *
* | * version No | *
* | * time | *
* | * server random | *
* | * session ID | *
* | * selected cypher suite | *
* | * selected compression | *
* | | *
* | (Certificate: if-not-anonymous) | *
* |<--------------------------------------------------------+ *
* | * certificate list | *
* | | *
* | (ServerKeyExchange: if-needed) | *
* |<--------------------------------------------------------+ *
* | * case RSA | *
* | Parameter N,E | *
* | Hash | *
* | * case Diffie-Helman | *
* | Parameter P,G,(G^X modP) | *
* | Hash | *
* | | *
* | (CertificationRequest) | *
* |<--------------------------------------------------------+ *
* | | *
* | ServerHelloDone | *
* |<--------------------------------------------------------+ *
* | | *
* | | *
* | (Certificate) | *
* +-------------------------------------------------------->| *
* | | *
* | ClientKeyExchange | *
* +-------------------------------------------------------->| *
* | | *
* | (CertificateVerify) | *
* +-------------------------------------------------------->| *
* | | *
* | ChangeCipherSpec | *
* +-------------------------------------------------------->| *
* | change the cipher suite | *
* | used by TLS Record Protocol | *
* | | *
* | Finished | *
* +-------------------------------------------------------->| *
* | | *
* | | *
* | ChangeCipherSpec | *
* |<--------------------------------------------------------+ *
* | | *
* | Finished | *
* |<--------------------------------------------------------+ *
* | | *
* | | *
* | | *
* |<<----------------------------------------------------->>| *
* | Application data protocol | *
* *
* *
* *
* *
* *
**********************************************************************************
##### Change Cipher Spec
This sub-protocol changes the keying material that is used for encryption between the client and server.
##### Alert
This sub-protocol uses messages to indicate a change in status or an error condition to the peer.
| Alert Message | Description |
|:---:|:--- |
| close_notify | Notifies the sender has closed session |
| unexpected_message | This message is always fatal. |
| bad_record_mac | Received a record with an incorrect MAC. (fatal) |
| decryption_failed | |
| record_overflow | |
| decompression_failure | |
| handshake_failure | |
| bad_certificate | |
| unsupported_certificate | Received an unsupported certificate type. |
| certificate_revoked | Received a certificate that was revoked by its signer. |
| certificate_expired | |
| certificate_unknown | An unspecified issue took place while processing the certificate that made it unacceptable. |
| illegal_parameter | Violated security parameters, such as a field in the handshake was out of range or inconsistent with other fields. This is always fatal. |
| unknown_ca | |
| access_denied | Received a valid certificate, but when access control was applied, the sender did not proceed with negotiation. |
| decode_error | |
| decrypt_error | |
| export_restriction | Detected a negotiation that was not in compliance with export restrictions; for example, attempting to transfer a 1024 bit ephemeral RSA key for the RSA_EXPORT handshake method. This message is always fatal. |
| protocol_version | The protocol version is not supported. |
| insufficient_security | Failed negotiation specifically because the server requires ciphers more secure than those supported by the client. |
| internal_error | An internal error unrelated to the peer or the correctness of the protocol makes it impossible to continue, such as a memory allocation failure. |
| user_canceled | |
| no_renegotiation | Sent by the client in response to a hello request or sent by the server in response to a client hello after initial handshaking. |
##### Application data protocol
this protocol established over TLS Record Protocol in order of application data communication
##### master secret
master secret is 46 byte number used for generating ;
* symmmetric encryption key
* message authentication code key
* init vector used at symmetric cypher CBC
# cryptography and society
## abstract
## bitcoin
## Quantum cryptography
this part is not reliable, depending what is not demonstrated yet .
## controlling various keys