SRM 480 Cryptography

Problem Statement TopCoder Security Agency (TSA, established today) has just invented a new encryption system! This encryption system takes as its input a list of numbers to encrypt. You work at TSA and your task is to implement a very important part of the encryption process. You are allowed to pick one number in the input list and increment its value by 1. This should be done in such way that the product of all numbers in the list after this change becomes as large as possible. Given the list of numbers as vector numbers, return the maximum product you can obtain. It is guaranteed that the return value will not exceed 2^62. Definition Class: Cryptography Method:encrypt Parameters:vector Returns:long long Method signature:long long encrypt(vector numbers) (be sure your method is public) Constraints – numbers will contain between 2 and 50 elements, inclusive. – Each element of numbers will be between 1 and 1000, inclusive. – The return value will not exceed 2^62. Examples 0) {1,2,3} Returns: 12 If we increment the first number, we get 2*2*3 = 12. If we increment the second, we get 1*3*3 = 9. If we increment the third, we get 1*2*4 = 8. Hence, the correct return value is 12. 1) {1,3,2,1,1,3} Returns: 36 The elements of numbers are not necessarily unique. 2) {1000,999,998,997,996,995} Returns: 986074810223904000 The answer may be very big, but will not exceed 2^62. 3) {1,1,1,1} Returns: 2 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.

#include <vector>
using namespace std;

class Cryptography {
    public:
        long long encrypt(vector <int> numbers) {
            long long ans = 0;

            for(int i=0; i<numbers.size(); i++) {
                long long seki=1;
                for (int j=0; j<numbers.length; j++){
                    if (i==j) {
                        seki *= (numbers[j] + 1);
                    } else {
                        seki *= numbers[j];
                    }
                }
                ans = max(ans, seki);
            }
            return ans;
        }
}

この問題は小さい数字に1を足す。その場合、増加率が最も大きくなる。

#include <vector>
#include <algorithm>
using namespace std;

class Cryptography {
    public:
        long long encrypt(vector <int> numbers) {
            long long ret = 1;
            sort(numbers.bigin(), numbers.end());
            numbers[0]++;

            for (int i = 0; i < number.size(); i++){
                ret *= numbers[i];
            }
            return ret;
        }
}

[C++/C] ポインタ

ポインタは変数のアドレスを持つ変数のこと
変数のアドレス場所を表すには、変数の頭に&をつける

ポインタ型とは、変数のアドレスを保存しておくための型
下記は同じ意味

char* test;
char *test;
#include <stdio.h>

int main(void) {

    char buf[50] = "bitcoin";
    char *test;

    test = buf;
    printf("%s", test);
    return 0;
}

文字列の後ろにつけるアスタリスクがあるのかと勘違いしてしまいますね。

[C++/C] uint256

uint256は256bitの符号付き整数型を宣言する
cpp uint256は、C++言語で使用される256ビットの符号なし整数型です。このデータ型は、非常に大きな整数値を扱うために使用されます。cpp uint256は、暗号通貨やブロックチェーンの開発において、特にハッシュ計算や暗号学的な操作に必要とされます。この型は、十進数や16進数などの異なる形式で整数を表現することもできます。cpp uint256は、その大きな範囲と精度のために、セキュリティや数値計算の要件を満たすために重要な役割を果たします。

The function uint256.ToString() is a method that convert a 256-bit unsigned integer into a string representation. This function is commonly used in cryptographic algorithms.

#include <iostream>
#include <string>

using namespace std;
using namespace boost::multiprecision;

int main() {
    
    uint256_t value = 1000000000000000000000000000000000000000000000000000000000000000;
    string str_value = value.ToString();
    cout << "Value as string: " << str_value << endl;
    return 0;
}


Boost.Multiprecisionから提供される多倍長整数

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;

int main() {
    
    mp::cpp_int x = 1;

    for (unsigned int i = 1; i <= 100; ++i) {
        x *= i;
    }

    std::cout << x << std::endl;
    return 0;
}

$ g++ -o sample sample.cpp && ./sample
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

[C++] iteratorとは?

イテレータとはコンテナ内での要素の位置を指すもので、ポインタのように扱うことができる。イテレータを使用することで、コンテナの種類に依存しないで処理を共通化できる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    
    vector<int> x = {0, 1, 2, 3, 4};

    // begin()でコンテナ内の先頭要素を指す
    auto it = x.begin();

    cout << *it << endl;

    ++it;

    cout << *it << endl;

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
0
1

end()は要素の1つ先となる。

    vector<int> x = {0, 1, 2, 3, 4};
    for (auto it = x.begin(); it != x.end(); ++it) {
        cout << *it << endl;
    }

    return 0;

この性質によってコンテナの種類に依存せず algorithmで提供される機能を使用できる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    
    vector<int> x = {0, 1, 2, 3, 4};
    auto n = std::count_if(x.begin(), x.end(), [](const int v){
        if (v <= 0) {
            return false;
        }
        if (v % 2 != 0){
            return false;
        }
        return true;
    });
    cout << n << endl;

    return 0;
}

[C++] endlとは

endl; とは出力の最後に改行を押し込むという意味

#include <iostream>
using namespace std;

int main() {
    
    cout << "I'm hpscript!" << endl;

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
I’m hpscript!

[C++] Ubuntu22.04にBoost install

Boost is a set of libraries for the C++ programming language that provides support for tasks and structures such as linear algebra, pseudorandom number generation, multithreading, image processing, regular expressions, and unit testing.

$ sudo apt-get install libboost-all-dev

#include <iostream>
#include <boost/version.hpp>

int main() {
    
    std::cout << "Ver." << BOOST_VERSION << '\n' <<
        "Lib Ver." << BOOST_LIB_VERSION << std::endl;

    return 0;
}

$ g++ -o sample sample.cpp && ./sample
Ver.107400
Lib Ver.1_74

[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