Category: cryptography

pkcs#5方式

ブロック暗号方式の場合、平文の文字数をブロック長の倍数に合わせるように、末尾に文字を足すなどの処理を行う必要がある。
ブロック暗号方式において文字を足すことをパディングと呼ぶ。

PKCS#7 パディングはRFC5652で定義されたパディング方式
pkcs#5　パディングは8バイトを倍数とした場合のパディング

なるほど、ちょっとモヤモヤしますな..

Rijndael-128とは

AESは鍵長128, 192, 256bitから選択できる
Rijndaelはブロック長も128, 192, 256bitから選択できる

$key = "秘密の合言葉";
$text = "暗号化するメッセージ";

srand();

$size = mcrypt_get_iv_size(MCRYPT_RIJNDAEL_128, MCRYPT_MODE_CBC);
$iv = mcrypt_create_iv($size, MCRYPT_RAND);

$encrypted = mcrypt_encrypt(MCRYPT_RIJNDAEL_128, $key, $text, MCRYPT_MODE_CBC, $iv);
$hex = bin2hex($encrypted);

$bin = pack("H*", $hex);
$decrptyed = mcrypt_decrypt(MCRYPT_RIJNDAEL_128, $key, $text, MCRYPT_MODE_CBC, $iv);

echo $text . "=>".rtrim($decrypted);

あれ、なんかおかしい。。

PythonでRSA暗号を実装したい

RSAは公開鍵暗号の一つ
暗号文 = 平文^E mod N {E, N}が公開鍵
平文 = 暗号文^D mod N {D, N}が秘密鍵

E, D, Nを求めるには素数を使う
N = p * q
L = lmc(p – 1, q – 1) # lmcとは最小公倍数(Least Common Multiple)
1 < E < L gcd(E,L) = 1 # gcdとは最大公約数、　E, Lは互いに素な整数 1 < D < L (E・D) mod L = 1 # DはEとの積の余剰が1となる任意の整数 

from math import gcd

def lcm(p, q):
	return (p * q) // gcd(p, q)

def generate_keys(p, q):
	N = p * q
	L = lcm(p – 1, q – 1)

	for i in range(2, L):
		if gcd(i, L) == 1:
			E = i
			break

	for i in range(2, L):
		if(E * i) % L == 1:
			D = i
			break

	return (E, N), (D, N)

def encrypt(plain_text, public_key):
	E, N = public_key
	plain_integers = [ord(char) for char in plain_text]
	encrypted_integers = [pow(i, E, N) for i in plain_integers]
	encrypted_text = ”.join(chr(i) for i in encrypted_integers)

	return encrypted_text

def decrypt(encrypted_text, private_key):
	D, N = private_key
	encrypted_integers = [ord(char) for char in encrypted_text]
	decrypted_integers = [pow(i, D, N) for i in encrypted_integers]
	decrypted_text = ”.join(chr(i) for i in decrypted_integers)

	return decrypted_text

def sanitize(encrypted_text):

	return encrypted_text.encode(‘utf-8’, ‘replace’).decode(‘utf-8’)

if __name__ == ‘__main__’:
	public_key, private_key = generate_keys(101, 3259)

	plain_text = ‘おはようございます’
	encrypted_text = encrypt(plain_text, public_key)
	decrypted_text = decrypt(encrypted_text, private_key)

	print(f”’
		秘密鍵: {public_key}
		公開鍵: {private_key}

		平文: 「{plain_text}」

		暗号文:
		「{sanitize(encrypted_text)}」

		平文(複合後):
		「{decrypted_text}」
		”'[1:-1])

なるほど、crypto currencyは暗号通貨ってことね

Mcrypt

This function is an extensive block algorithm such as CBC, OFB, CFB, ECB cipher modes DES, TripleDES, Blowfish (default), 3-WAY, SAFER-SK64, SAFER-SK128, TWOFISH, TEA, RC2 and GOST. Interface to the mcrypt library to support. In addition, it supports RC6 and IDEA, which are described as “not free”.

Alice and Bob

from urllib import urlopen, urlencode
import json

base = "http://hgehoge.com"
Alice = base + "/alice"
Bob = base + "bob"

def check_output(output):
	data = output.read()
	if output.getcode() != 200:
		raise Exception(data)
	data = json.loads(data)
	return data

def get_pg():
	output = urlopen(base)
	data = check_output(output)
	return data

def initialize(person):
	data = {'type':'init'}
	output = urlopen(person, urlencode(data))
	data = check_output(output)
	return data

def send_key(person, token, public, name):
	data = {'type':'key',
		'token':token,
		'public': public,
		'name':name}
	output = urlopen(person, urlencode(data))
	data = check_output(output)
	return data

daf recieve_msg(person, token):
	data = {'type':'msg',
			'token':token}
	output = urlopen(person, urlencode(data))
	data = check_output(output)
	return data

def send_msg(person, token, cipher, iv):
	data = {'type':'msg',
			'token':token,
			'message':cipher,
			'iv':iv}
	output = urlopen(person, urlencode(data))
	data = check_output(output)
	return data

a≡b (mod c)

a≡b (mod c)　は a-bがcで割り切れること。
10≡0 (mod 5)
14≡5 (mod 3)
13≡-3 (mod 2)

from Crypto.Util.number import inverse
def message_value(message):
	message = bits_to_string(pad_to_block(convert_to_bits(message), 8))
	return cutchoose.bill_value(message)

def remove_nonce(bill, nonce):
	big_nonce = pow(nonce, cutchoose.BANK_PUBLIC_KEY[0], cutchoose.BANK_PUBLIC_KEY[1])
	nonce_inverse = inverse(big_nonce, cutchoose.BANK_PUBLIC_KEY[1])
	message = (bill * nonce_inverse) % cutchoose.BANK_PUBLIC_KEY[1]
	return message

def _verify(bills, nonces, value):
	for bill, nonce in zip(bills, nonces):
		message = remove_nonce(Bill, nonce)
		test_value = message_value(message)
		if test_value != value:
			return False

Cut and choose

import cutchoose
from unit6_util import string_to_bits, bits_to_int, pad_to_block, bits_to_string, convert_to_bit

def _verify(bills, nonces, value):
	return False
cutchoose.verify = _verify

def test():
	bills = cutchoose.generate_bills(50)
	i = cutchoose.pick_and_sign_bills(bills)
	nonces = cutchoose.send_nonces(i)
	signed = cutchoose.verify_bills_and_return_signed(nonces, 50)
	assert signed is not None 
	assert bills[i] == pow(signed, cutchoose.BANK_PUBLIC_KEY[0],
						cutchoose.BANK_PUBLIC_KEY[1])

	bills = cutchoose.cheat_generate_bills(50, 100)
	i = cutchoose.pick_and_sign_bills(bills)
	nonces = cutchoose.send_nonces(i)
	signed = cutchoose.verify_bills_and_return_signed(nonces, 50)
	assert signed is None

beast attack

import urllib
import json
import base64

BLOCK_SIZE = 128
site = "http://cs387.udacity-extras.appspot.com/beast"

def unencode_json(txt):
	d = json.loads(txt)
	return dict((str(k),
		base64.urlsafe_b64decode(str(v)))
		for k, v in d.iteritems())

def _send(attack=None, token=None):
	data = {}
	if attack is not None:
		data["attack"] = base64.urlsafe_b64encode(attack)
	if token is not None:
		data["token"] = base64.urlsafe_b64encode(token)

	json = urllib.urlopen(site, urllib.urlencode(data)).read()
	json = unencode_json(json)
	return json

_TOKEN = None
def send(attack=None):
	global _TOKEN
	json = _send(attack, _TOKEN)
	_TOKEN = json["token"]
	return json["message"]

Asymmetric Cryptosystems

e = 65537
n = 132177882185373774813945506243321607011510930684897434818595314234725602493934515403833460241072842788085178405842019124354553719616350676051289956113618487539608319422698056216887276531560386229271076862408823338669795520077783060068491144890490733649000321192437210365603856143989888494731654785043992278251

m1 = 387
s1 = 104694095966994423550399840405679271451689287439740118881968798612714798360187905616965324945306116261186514828745033919423253353071142760352995900515279740753864505327750319034602409274084867637277266750899735986681083836544151016817569622466120342654469777762743360212628271549581658814852850038900877029382

m2 = 2
s2 = 18269259493999292542402899855086766469838750310113238685472900147571691729574239379292239589580462883199555239659513821547589498977376834615709314449943085101697266417531578751311966354219681199183298006299399765358783274424349074040973733214578342738572625956971005052398172213596798751992841512724116639637

m3 = 774
s3 = 0

def mod_exp(a, b, q):
	val = 1
	mult = a
	while b > 0:
		odd = b & 1
		if odd == 1:
			val = (val * mult) % q
			b -= 1
		if b == 0:
			break
		mult = (mult * mult) % q
		b = b >> 1
	return val

def verify_signature(e, n, m, s):
	assert m == mod_exp(s, e, n)

Diffie-Hellman key exchange

import string
P = 1267650600228229401496703205223 
g = 3
g_a = 142621255265782287951127214876
g_b = 609743693736442153553407144551
n_multiplications = 26

def mod_exp(a, b, q):
	"""return a**b % q"""
	val = 1
	mult = a
	while b > 0
		add = b & 1
		if odd == 1:
			val = (val * mult) % q
			b -= 1
		if b == 0:
			break
		mult = (mult * mult) % q
		b = b >> 1
	return val

def count_multiplications(exponent):
	"""return the number of multiplications
	necessary to raise a number to 'exponent'"""
	bits = convert_to_bits(exponent)
	return len(bits) + sum(b for b in bits) -2

def encode(plaintext, key):
	assert len(plaintext) <= len(key)
	return &#91;m^k for m, k in zip(plaintext, key)&#93;

def decode(ciphertext, key):
	assert len(ciphertext) <= len(key)
	return &#91;c^k for c, k in zip(ciphertext, key)&#93;

valid_chars = set(c for c in string.printable&#91;:62&#93;)
valid_chars.add('')
def is_valid(decode_guess):
	return (len(decode_guess) == 14 and
		all(d in valid_chars for d in decode_guess))

BITS = ('0', '1')
ASCII_BITS = 7 

def display_bits(b):
    """converts list of {0, 1}* to string"""
    return ''.join(&#91;BITS&#91;e&#93; for e in b&#93;)

def seq_to_bits(seq):
    return &#91;0 if b == '0' else 1 for b in seq&#93;

def pad_bits(bits, pad):
    """pads seq with leading 0s up to length pad"""
    assert len(bits) <= pad
    return &#91;0&#93; * (pad - len(bits)) + bits
        
def convert_to_bits(n):
    """converts an integer `n` to bit array"""
    result = &#91;&#93;
    if n == 0:
        return &#91;0&#93;
    while n > 0:
        result = [(n % 2)] + result
        n = n / 2
    return result

def string_to_bits(s):
    def chr_to_bit(c):
        return pad_bits(convert_to_bits(ord(c)), ASCII_BITS)
    return [b for group in 
            map(chr_to_bit, s)
            for b in group]

def bits_to_char(b):
    assert len(b) == ASCII_BITS
    value = 0
    for e in b:
        value = (value * 2) + e
    return chr(value)

def list_to_string(p):
    return ''.join(p)

def bits_to_string(b):
    return ''.join([bits_to_char(b[i:i + ASCII_BITS]) 
                    for i in range(0, len(b), ASCII_BITS)])