Month: December 2023

[C++/C] mapとは

mapはvector同様、配列の一種。
vectorが要素へのアクセスを0, 1, 2…といったインデックスで行っている一方、mapはキーが要素隣、連想配列とも言われる。

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    map <string, int> score;
    string names[] = {"Tom", "Bob", "Mike"};
    score[names[0]] = 100;
    score[names[1]] = 80;
    score[names[2]] = 120;
    int i;
    for(i = 0; i < 3; i++){
        cout << names[i] << ":" << score[names[i]] << endl;
    }
    return 0;
}

$ g++ -o sample sample.cpp && ./sample
Tom:100
Bob:80
Mike:120

[C++/C] external宣言

C言語において、extern宣言はグローバル変数を共有する仕組み

グローバル変数とローカル変数

#include <stdio.h>

int gNumber = 100;

void func(void) {
    gNumber += 100;
}

int main(void) {
    int tmp = 100;

    func();

    printf("tmp : %d\n", tmp);
    printf("gNumber : %d\n", gNumber);
}

$ gcc test.c -o test && ./test
tmp : 100
gNumber : 200

複数ファイルにする
main.c

#include <stdio.h>

void func();

int main(void) {

    func();
    printf("gNumber : %d\n", gNumber);
}

sub.c

int gNumber = 100;

void func(void) {
    gNumber += 100;
}

この場合、sub.cのコンパイルは通るがmain.cのコンパイル時にgNumberが定義されていない識別子としてエラーになる。
$ gcc -c sub.c
$ gcc -c main.c
main.c: In function ‘main’:
main.c:8:30: error: ‘gNumber’ undeclared (first use in this function)
8 | printf(“gNumber : %d\n”, gNumber);
| ^~~~~~~
main.c:8:30: note: each undeclared identifier is reported only once for each function it appears in

そこでmain.cでexternで宣言する

#include <stdio.h>

extern int gNumber;
void func();

int main(void) {

    func();
    printf("gNumber : %d\n", gNumber);
}

$ gcc -c main.c
$ gcc main.o sub.o -o main
$ ./main
gNumber : 200

[bitcoin基礎技術] デジタル署名

<送信者>
– データをハッシュ関数でハッシュ化
– 出力されたハッシュ値を秘密鍵で暗号化し、署名を作成
– データと署名をセットにして受信者に送信

<受信者>
– 受け取ったデータを送信者と同じハッシュ関数でハッシュ化してハッシュ値Aを得る
– 受け取った署名を送信者の公開鍵で復号してハッシュ値Bを得る
– A B比較して一致していることを確認

### デジタル署名の流れ
1. 送信者のメッセージを作成
$ echo secret > message.txt; cat message.txt
secret

2. 秘密鍵でハッシュ値に署名し、message.sigに出力
$ openssl dgst -sha256 -sign secp256k1-private.pem message.txt > message.sig; ls message.sig
message.sig

3. 生成した公開鍵で署名を検証
$ openssl dgst -sha256 -verify secp256k1-public.pem -signature message.sig message.txt
Verified OK

### メッセージの改ざん検出
$ openssl ecparam -genkey -name secp256k1 -out secp256k1-private-evil.pem; ls secp256k1-private-evil.pem
secp256k1-private-evil.pem
$ echo “tampered secret” > tampered_message.txt ; cat tampered_message.txt
tampered secret
$ openssl dgst -sha256 -sign secp256k1-private-evil.pem tampered_message.txt > tampered_message.sig ; ls tampered_message.sig
tampered_message.sig
$ openssl dgst -sha256 -verify secp256k1-public.pem -signature tampered_message.sig tampered_message.txt
Verification failure

[bitcoin基礎技術] 公開鍵暗号

パラメータファイルの生成
$ openssl ecparam -name secp256k1 -out secp256k1.pem

secp256k1.pem

-----BEGIN EC PARAMETERS-----
BgUrgQQACg==
-----END EC PARAMETERS-----

$ openssl ecparam -in secp256k1.pem -text -noout
EC-Parameters: (256 bit)
ASN1 OID: secp256k1

パラメータの確認
$ openssl ecparam -in secp256k1.pem -text -param_enc explicit -noout
EC-Parameters: (256 bit)
Field Type: prime-field
Prime:
00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:fe:ff:
ff:fc:2f
A: 0
B: 7 (0x7)
Generator (uncompressed):
04:79:be:66:7e:f9:dc:bb:ac:55:a0:62:95:ce:87:
0b:07:02:9b:fc:db:2d:ce:28:d9:59:f2:81:5b:16:
f8:17:98:48:3a:da:77:26:a3:c4:65:5d:a4:fb:fc:
0e:11:08:a8:fd:17:b4:48:a6:85:54:19:9c:47:d0:
8f:fb:10:d4:b8
Order:
00:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:ff:
ff:fe:ba:ae:dc:e6:af:48:a0:3b:bf:d2:5e:8c:d0:
36:41:41
Cofactor: 1 (0x1)

秘密鍵を生成
$ openssl ecparam -in secp256k1.pem -genkey -noout -out secp256k1-private.pem
$ cat secp256k1-private.pem
—–BEGIN EC PRIVATE KEY—–
MHQCAQEEIAqV2IN8gUr9qXpsJyhpYA4KQfXioS/oiDMh1dgPcncAoAcGBSuBBAAK
oUQDQgAEeiuKeXTtb0t4F7DzVMbIHOrLIQ5T4JPq3NTU7OC7TWCghk6ALrWLgTGD
zUuuEIWI4GLsYea/829orVMO4Rz/FQ==
—–END EC PRIVATE KEY—–

秘密鍵を16進数表記で出力
$ openssl ec -in secp256k1-private.pem -outform DER | tail -c +8 | head -c 32 | xxd -p -c 32
read EC key
writing EC key
0a95d8837c814afda97a6c272869600e0a41f5e2a12fe8883321d5d80f727700

秘密鍵を変数に格納
$ privKey=0a95d8837c814afda97a6c272869600e0a41f5e2a12fe8883321d5d80f727700

公開鍵を生成
$ openssl ec -in secp256k1-private.pem -pubout -out secp256k1-public.pem; cat secp256k1-public.pem
read EC key
writing EC key
—–BEGIN PUBLIC KEY—–
MFYwEAYHKoZIzj0CAQYFK4EEAAoDQgAEeiuKeXTtb0t4F7DzVMbIHOrLIQ5T4JPq
3NTU7OC7TWCghk6ALrWLgTGDzUuuEIWI4GLsYea/829orVMO4Rz/FQ==

公開鍵を16進数で出力
$ openssl ec -in secp256k1-private.pem -pubout -outform DER | tail -c 65 | xxd -p -c 65
read EC key
writing EC key
047a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15

秘密鍵はスカラーですが、公開鍵は座標x, y
$ pubKey=047a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15
$ prefix=`echo $pubKey | cut -c1-2`; echo “prefix= $prefix”
prefix= 04
$ x=`echo $pubKey | cut -c3-66` ; echo “x = $x”
x = 7a2b8a7974ed6f4b7817b0f354c6c81ceacb210e53e093eadcd4d4ece0bb4d60
$ y=`echo $pubKey | cut -c67-130`; echo “y= $y”
y= a0864e802eb58b813183cd4bae108588e062ec61e6bff36f68ad530ee11cff15

[C++ basic] 出力, 文字数字

#include <iostream>
using namespace std;

int main() {
    cout << "ようこそC++!\n";
    cout << "lets start c++!\n";

    return 0;
}

coutはstandard outputと結び付けられ、 は表示を意味する
iostreamは画面出力の機能などを表す
coutは本来、using namespace stdでstc.coutと書くが、省略もできる。

int main() {
    cout << 1 << 2 << 3 << '\n' << 4 << 5 << '\n';

    return 0;
}

c++では文字、数字の表記をリテラルと呼ぶ。リテラルの他に、キーワード、識別子、演算子、区切り子などがある。
リテラルは”で囲む

#include <iostream>
using namespace std;

int main() {
    cout << 'A' << '\n';
    cout << "welcome to C++!\n";
    cout << 123 << '\n';

    return 0;
}

エスケープシーケンス

int main() {

    cout << "円記号を表示する:" << '\\' << '\n';
    cout << "アポストロフィを表示する:" << '\'' << '\n';

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
円記号を表示する:\
アポストロフィを表示する:’

文字コード

int main() {

    cout << "8進数101の文字コードを持つ文字は" << '\101' << "です\n";
    cout << "16進数61の文字コードを持つ文字は" << '\x61' << "です\n";

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
8進数101の文字コードを持つ文字はAです
16進数61の文字コードを持つ文字はaです

文字リテラルは”でくくる。
数値には整数と浮動小数点があり、それぞれinteger literal, floating literalと呼ぶ

int main() {

    cout << "10進数の10は" << 10 << "です\n";
    cout << "8進数の10は" << 010 << "です\n";
    cout << "16進数の10は" << 0x10 << "です\n";
    cout << "16進数のFは" << 0xF << "です\n";

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
10進数の10は10です
8進数の10は8です
16進数の10は16です
16進数のFは15です

int main() {

    cout <<  123 << '\n';
    cout << "\\" << "100もらった\n";
    cout << "また明日\n";

    return 0;
}

8進数と16進数

#include <iostream>
using namespace std;

int main() {

    // 8進数
    cout <<  06 << '\n';
    cout <<  024 << '\n';
    cout <<  015 << '\n';

    // 16進数
    cout <<  0x6 << '\n';
    cout <<  0x14 << '\n';
    cout <<  0xd << '\n';
}

16進数はビットコインで基本となってますね。

coding practice SRM494

Mr. White is a very versatile person – absolutely everything is interesting to him. Perhaps this is why he has many friends. Quite unfortunately, however, none of his friends are versatile at all. Each of them is interested only in two topics and refuses to talk about anything else. Therefore, each time Mr. White organizes a party, it’s a big problem for him to decide whom to invite so that the party is interesting to everybody. Now that Mr. White has a lot of experience in organizing parties, he knows for sure that a party will be interesting if and only if there’s a topic interesting to each of the invited friends.

#include <vector>
#include <string>
using namespacee std;

class InterestingParty {
    public:
        int bestInvitation(vector <string> first, vector <string> second) {
            int i, j;
            int ans = 0;

            for(i=0; i<first.size(); i++){
                int f=0;
                int s=0;
                for(j=0; j<first.size(); j++){
                    if(first[i] == first[j]) f++;
                    if(first[i] == second[j]) f++;
                    if(second[i] == first[j]) s++;
                    if(second[i] == second[j]) s++;
                }
                ans = max(f, ans);
                ans = max(s, ans);
            }
            return ans;
        }
}

連想配列を使う場合

#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespacee std;

class InterestingParty {
    public:
        int bestInvitation(vector <string> first, vector <string> second) {
            map <string, int> dic;

            for(int i=0; i<first.size(); i++){
                dic[first[i]] = 0;
                dic[second[i]] = 0;
            }

            for(int i=0; i<first.size; i++){
                dic[first[i]]++;
                dic[second[i]]++;
            }
            int ans = 0;
            map <string, int>::iterator it;
            for(it=dic.begin(); it!=dic.end(); it++){
                ans = max(ans, it->second);
            }
            return ans;
        }
}

[bitcoin基礎技術] sha256, ripemd160, HMAC-SHA512, PBKDF2

### SHA-256
常に32bytesで出力される
$ echo -n abcdefghijklmn | openssl dgst -sha256
SHA2-256(stdin)= 0653c7e992d7aad40cb2635738b870e4c154afb346340d02c797d490dd52d5f9
-n は改行出力を抑止
$ echo -n a | openssl dgst -sha256
SHA2-256(stdin)= ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

### RIPEMD-160
160bit 20bytes
$ echo -n a | openssl dgst -rmd160
Error setting digest
2070E0ADFFFF0000:error:0308010C:digital envelope routines:inner_evp_generic_fetch:unsupported:../crypto/evp/evp_fetch.c:349:Global default library context, Algorithm (RIPEMD160 : 99), Properties ()
2070E0ADFFFF0000:error:03000086:digital envelope routines:evp_md_init_internal:initialization error:../crypto/evp/digest.c:254:

$ apt list openssl
Listing… Done
openssl/jammy-updates,jammy-security,now 3.0.2-0ubuntu1.12 arm64 [installed,automatic]

ubuntu22.04でopenssl3.0.2だと ripemd160が使えないらしい

### ダブルハッシュ
$ echo -n a | xxd -r -p | openssl dgst -sha256 | openssl dgst -rmd160
xxd -r -pでバイナリデータに変換する
$ echo -n a | xxd -r -p | openssl dgst -sha256 | openssl dgst -sha256
SHA2-256(stdin)= e877d81a8f216a6aebe39b3ca7b350ad38db6d8ea6ad7e3fe581a8a1ab09eeee

### HMAC-SHA512
HMAC-SHA512とはキーとデータのペアを入力してハッシュ化する処理のこと
SHA-512を使用する
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -hmac “Jefe”
SHA2-512(stdin)= 164b7a7bfcf819e2e395fbe73b56e0a387bd64222e831fd610270cd7ea2505549758bf75c05a994a6d034f65f8f0e6fdcaeab1a34d4a6b4b636e070a38bce737
キーを16進数で指定する場合は以下の通り
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:4a656665
SHA2-512(stdin)= 164b7a7bfcf819e2e395fbe73b56e0a387bd64222e831fd610270cd7ea2505549758bf75c05a994a6d034f65f8f0e6fdcaeab1a34d4a6b4b636e070a38bce737

ワンライナーで表示
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:`echo -n Jefe | xxd -p`
$ echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:$(echo -n Jefe | xxd -p)
hmac=`echo -n “what do ya want for nothing?” | openssl dgst -sha512 -mac HMAC -macopt hexkey:$(echo -n Jefe | xxd -p)`; echo $hmac

### PBKDF2
一般的にパスワードのハッシュ化に利用される
ビットコインではニモニックコードからシードを生成する際に利用される。
PBKDF2ではキーとデータを入力し、使用するハッシュ関数とストレッチングの回数を決めておく

import hashlib, binascii
hashFunc="sha512"
password=b"passw0rd"
salt=b"bitcoin"
iteCnt=100
encPass=hashlib.pbkdf2_hmac(hashFunc, password, salt, iteCnt)
print(binascii.hexlify(encPass))

$ python3 main.py
b’65252733b1f1d6e5abd4474d696989641125bedb34be2c7789eef454abac6e718180666c73e0ec44ed529291e3b6e5b22d4222b263c259aa0128ad9f5e1cd2c2′

Ubuntu22.04でc++の実行環境を作る

$ sudo apt install build-essential
$ gcc –version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ g++ –version
g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

#include <iostream>
using namespace std;

int main() {
    cout << "ようこそC++!\n";

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
ようこそC++!

sig_hashとverify_input

txをシリアライズする際に、redeem_script=None としてp2pkh か p2shかを分ける

    def sig_hash(self, input_index, redeem_script=None):
        s = int_to_little_endian(self.version, 4)
        s += encode_varint(len(self.tx_ins))
        for i, tx_in in enumerate(self.tx_ins):
            if i == input_index:
                if redeem_script:
                    script_sig = redeem_script
                else:
                    script_sig = tx_in.script_pubkey(self.testnet)
            else:
                script_sig = None    
            s += TxIn(
                prev_tx = tx_in.prev_tx,
                prev_index = tx_in.prev_index,
                script_sig = tx_in.script_pubkey(self.testnet),
                sequence = tx_in.sequence,
            ).serialize()
        s += encode_varint(len(self.tx_outs))
        for tx_out in self.tx_outs:
            s += tx_out.serialize()
        s += int_to_little_endian(self.locktime, 4)
        s += int_to_little_endian(SIGHASH_ALL, 4)
        h256 = hash256(s)
        return int.from_bytes(h256, 'big')

    def verify_input(self, input_index):
        tx_in = self.tx_ins[input_index]
        script_pubkey = tx_in.script_pubkey(testnet=self.testnet)
        if script_pubkey.is_p2sh_script_pubkey():
            cmd = tx_in.script_sig.cmds[-1]
            raw_redeem = encode_varint(len(cmd)) + cmd
            redeem_script = Script.parse(BytesIO(raw_redeem))
        else:
            redeem_script = None
        z = self.sig_hash(input_index, redeem_script)
        combined = tx_in.script_sig + script_pubkey
        return combined.evaluate(z)

    def is_p2pkh_script_pubkey(self):
        return len(self.cmds) == 5 and self.cmds[0] == 0x76 \
            and self.cmds[1] == 0xa9 \
            and type(self.cmds[2]) == bytes and len(self.cmds[2]) == 20 \
            and self.cmds[3] == 0x88 and self.cmds[4] == 0xac

    def is_p2sh_script_pubkey(self):
        return len(self.cmds) == 3 and self.cmds[0] == 0xa9 \
            and type(self.cmds[1]) == bytes and len(self.cmds[1]) == 20 \
            adn self.cmds[2] == 0x87