暗号技術Advent Calendar 2024

@SiZKin

Qiita株式会社

視覚復号型秘密分散法実装編

Last updated at 2024-12-25Posted at 2024-12-25

はじめに

前回の記事で視覚復号型秘密分散法の説明をしました。

今回は、視覚復号型秘密分散法を Rust で実装していきます。

視覚復号型秘密分散法の実装

バイナリ画像の読み書き

まずは、バイナリ画像を読み込んだり書き込んだりできるようにします。
この辺りは各言語適当なライブラリを使えば良いので、適当に読み飛ばしてもらって問題ありません。

読み込んだ画像を二値の白黒画像に変換し、それを boolean 配列にする関数を定義します。
このとき true が黒で、false が白となるようにしています。

fn read_image(path: &Path) -> Array2<bool> {
    let img = image::ImageReader::open(path).unwrap().decode().unwrap();
    let mut img = img.grayscale().to_luma8();
    image::imageops::dither(&mut img, &image::imageops::BiLevel);

    let height = img.height().try_into().unwrap();
    let width = img.width().try_into().unwrap();
    Array::from_shape_vec(
        (height, width),
        img.into_vec().iter().map(|&pixel| pixel == 0).collect(),
    )
    .unwrap()
}

逆に boolean の配列を二値の白黒画像とみなして、画像を書き出す関数も定義しておきます。

fn write_image(img: &Array2<bool>, path: &Path) {
    let height = img.nrows().try_into().unwrap();
    let width = img.ncols().try_into().unwrap();
    let buf = img
        .flatten()
        .map(|&flag| if flag { 0 } else { 255 })
        .to_vec();

    image::save_buffer(path, &buf, width, height, image::ExtendedColorType::L8).unwrap();
}

これで秘密分散を行うための準備ができました。

サブピクセルの定義

まずは $(k, n)$ 視覚復号型秘密分散法を表す構造体 VisualSecretSharing を定義します。

struct VisualSecretSharing<const K: usize, const N: usize> {}

今回は任意の $(k, n)$ に対応するわけではないので、サブピクセルの trait を定義して、それを実装している型のみで、秘密分散を行えるようにしていきます。

trait Subpixel {
    const C0: LazyCell<Array2<bool>>;
    const C1: LazyCell<Array2<bool>>;
    const M_ROW: usize;
    const M_COL: usize;

    fn subpixel(&self, secret: bool) -> Array2<bool> {
        let subpixel = if secret { &*Self::C1 } else { &*Self::C0 };

        random_permutation(subpixel)
    }
}

C0 と C1 が定義してあれば subpixel メソッドを呼び出せるようにしています。
また M_ROW と M_COL は、サブピクセルの行数と列数です。

あとは random_permutation を定義して、サブピクセルの列をランダムに入れ替えるようにます。

fn random_permutation(matrix: &Array2<bool>) -> Array2<bool> {
    let mut rng = rand::thread_rng();
    let mut perm: Vec<usize> = (0..matrix.ncols()).collect();
    perm.shuffle(&mut rng);

    matrix.select(Axis(1), &perm)
}

$(2, 2)$ と $(3, 4)$ の違いはサブピクセルの部分だけなので、異なる部分の実装をここで一気に終わらせます。

(2, 2) 視覚復号型秘密分散法のサブピクセルの実装

VisualSecretSharing<2, 2> に対して Subpixel trait を実装します。

impl Subpixel for VisualSecretSharing<2, 2> {
    const C0: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [false, true]]));
    const C1: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [true, false]]));
    const M_ROW: usize = 1;
    const M_COL: usize = 2;
}

(3, 4) 視覚復号型秘密分散法のサブピクセルの実装

同様に VisualSecretSharing<2, 2> に対して Subpixel trait を実装します。

impl Subpixel for VisualSecretSharing<3, 4> {
    const C0: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [false, false, false, true, true, true],
            [false, false, true, false, true, true],
            [false, false, true, true, false, true],
            [false, false, true, true, true, false],
        ])
    });
    const C1: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [true, true, true, false, false, false],
            [true, true, false, true, false, false],
            [true, true, false, false, true, false],
            [true, true, false, false, false, true],
        ])
    });
    const M_ROW: usize = 2;
    const M_COL: usize = 3;
}

シェアの生成

サブピクセルの実装が終わっていれば、シェアの生成は難しくありません。

一つ一つのピクセルに対して subpixel メソッドを実行していくだけです。
したがって、元の画像の大きさを $H \times W$ とすると、シェア画像の大きさは $H M_{ROW} \times W M_{COL}$ になります。

impl<const K: usize, const N: usize> VisualSecretSharing<K, N>
where
    Self: Subpixel,
{
    fn generate_shares(&self, secret: &Array2<bool>) -> Array3<bool> {
        let (height, width) = secret.dim();

        let mut shares = Array::from_elem((N, Self::M_ROW * height, Self::M_COL * width), false);

        for ((x, y), &pixel) in secret.indexed_iter() {
            shares
                .slice_mut(ndarray::s![
                    ..,
                    Self::M_ROW * x..Self::M_ROW * (x + 1),
                    Self::M_COL * y..Self::M_COL * (y + 1)
                ])
                .assign(
                    &self
                        .subpixel(pixel)
                        .to_shape((N, Self::M_ROW, Self::M_COL))
                        .unwrap(),
                );
        }

        shares
    }
}

秘密情報の再構成

再構成は、計算機が無くてもできるようになっており、計算機での処理もかなり簡単です。
シェア画像で同じ位置にあるピクセルの論理和を取れば良いだけです。

実世界で再構成をする場合は、シェア画像を透明なシートに印刷して、そのシート同士を重ね合わせるというのが一般的です。

impl<const K: usize, const N: usize> VisualSecretSharing<K, N>
where
    Self: Subpixel,
{
    fn reconstruct(&self, shares: &Array3<bool>) -> Array2<bool> {
        let (_, height, width) = shares.dim();
        let mut img = Array::from_elem((height, width), false);

        for share in shares.outer_iter() {
            img.zip_mut_with(&share, |x, &y| {
                *x |= y;
            });
        }

        img
    }
}

動作確認

ここでは $(3, 4)$ の方で見ていきます。

let secret = read_image(Path::new("secret.bmp"));

let vss = VisualSecretSharing::<3, 4> {};

let shares = vss.generate_shares(&secret);
for (i, share) in shares.outer_iter().enumerate() {
    write_image(
        &share.to_owned(),
        Path::new(&format!("share_{:02}.bmp", i + 1)),
    );
}

秘密情報 secret.bmp として以下の画像を使いました。

そうすると、シェア画像は以下のように出力されました。

1 つ目	2 つ目	3 つ目	4 つ目

少なくとも、人の目でみたときに元の情報は分かりません。
2 つのシェアを重ねたものがどうなるかを見てみます。

let reconstructed_secret_from_2_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1]));
write_image(
    &reconstructed_secret_from_2_shares,
    Path::new("reconstructed_secret_from_2_shares.bmp"),
);

先ほどのシェア画像の 1, 2 番目を重ねたものが以下です。

これも、まだ元の情報は分かりません。
$(3, 4)$ 視覚復号型秘密分散法なので、今のところ挙動は正しそうです。

3 つのシェアを重ねたときに、元の情報が分かるようになれば良さそうです。

let reconstructed_secret_from_3_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1, 2]));
write_image(
    &reconstructed_secret_from_3_shares,
    Path::new("recontructed_secret_from_3_shares.bmp"),
);

先ほどのシェア画像の 1, 2, 3 番目を重ねたものが以下です。

相対差が小さいですが、元の情報が読み取れるようになっています。

4 つのシェアを重ねた場合も見てみます。

let reconstructed_secret_from_all_shares = vss.reconstruct(&shares);
write_image(
    &reconstructed_secret_from_all_shares,
    Path::new("recontructed_secret_from_all_shares.bmp"),
);

先ほどのシェア画像を全部重ねたものが以下です。

先ほどより、くっきりと黒が見えるようになっています。
理論的には、3 つ重ねた場合の相対差が 1 で、4 つ重ねた場合の相対差が 2 なので、実際にそのようになっていそうなことが分かります。

全体のコード

use ndarray::{Array, Array2, Array3, Axis};
use rand::seq::SliceRandom;
use std::{cell::LazyCell, path::Path};

fn read_image(path: &Path) -> Array2<bool> {
    let img = image::ImageReader::open(path).unwrap().decode().unwrap();
    let mut img = img.grayscale().to_luma8();
    image::imageops::dither(&mut img, &image::imageops::BiLevel);

    let height = img.height().try_into().unwrap();
    let width = img.width().try_into().unwrap();
    Array::from_shape_vec(
        (height, width),
        img.into_vec().iter().map(|&pixel| pixel == 0).collect(),
    )
    .unwrap()
}

fn write_image(img: &Array2<bool>, path: &Path) {
    let height = img.nrows().try_into().unwrap();
    let width = img.ncols().try_into().unwrap();
    let buf = img
        .flatten()
        .map(|&flag| if flag { 0 } else { 255 })
        .to_vec();

    image::save_buffer(path, &buf, width, height, image::ExtendedColorType::L8).unwrap();
}

fn random_permutation(matrix: &Array2<bool>) -> Array2<bool> {
    let mut rng = rand::thread_rng();
    let mut perm: Vec<usize> = (0..matrix.ncols()).collect();
    perm.shuffle(&mut rng);

    matrix.select(Axis(1), &perm)
}

struct VisualSecretSharing<const K: usize, const N: usize> {}

trait Subpixel {
    const C0: LazyCell<Array2<bool>>;
    const C1: LazyCell<Array2<bool>>;
    const M_ROW: usize;
    const M_COL: usize;

    fn subpixel(&self, secret: bool) -> Array2<bool> {
        let subpixel = if secret { &*Self::C1 } else { &*Self::C0 };

        random_permutation(subpixel)
    }
}

impl Subpixel for VisualSecretSharing<2, 2> {
    const C0: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [false, true]]));
    const C1: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [true, false]]));
    const M_ROW: usize = 1;
    const M_COL: usize = 2;
}

impl Subpixel for VisualSecretSharing<3, 4> {
    const C0: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [false, false, false, true, true, true],
            [false, false, true, false, true, true],
            [false, false, true, true, false, true],
            [false, false, true, true, true, false],
        ])
    });
    const C1: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [true, true, true, false, false, false],
            [true, true, false, true, false, false],
            [true, true, false, false, true, false],
            [true, true, false, false, false, true],
        ])
    });
    const M_ROW: usize = 2;
    const M_COL: usize = 3;
}

impl<const K: usize, const N: usize> VisualSecretSharing<K, N>
where
    Self: Subpixel,
{
    fn generate_shares(&self, secret: &Array2<bool>) -> Array3<bool> {
        let (height, width) = secret.dim();

        let mut shares = Array::from_elem((N, Self::M_ROW * height, Self::M_COL * width), false);

        for ((x, y), &pixel) in secret.indexed_iter() {
            shares
                .slice_mut(ndarray::s![
                    ..,
                    Self::M_ROW * x..Self::M_ROW * (x + 1),
                    Self::M_COL * y..Self::M_COL * (y + 1)
                ])
                .assign(
                    &self
                        .subpixel(pixel)
                        .to_shape((N, Self::M_ROW, Self::M_COL))
                        .unwrap(),
                );
        }

        shares
    }

    fn reconstruct(&self, shares: &Array3<bool>) -> Array2<bool> {
        let (_, height, width) = shares.dim();
        let mut img = Array::from_elem((height, width), false);

        for share in shares.outer_iter() {
            img.zip_mut_with(&share, |x, &y| {
                *x |= y;
            });
        }

        img
    }
}

fn main() {
    let secret = read_image(Path::new("secret.bmp"));

    let vss = VisualSecretSharing::<3, 4> {};

    let shares = vss.generate_shares(&secret);
    for (i, share) in shares.outer_iter().enumerate() {
        write_image(
            &share.to_owned(),
            Path::new(&format!("share_{:02}.bmp", i + 1)),
        );
    }

    let reconstructed_secret_from_2_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1]));
    write_image(
        &reconstructed_secret_from_2_shares,
        Path::new("reconstructed_secret_from_2_shares.bmp"),
    );

    let reconstructed_secret_from_3_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1, 2]));
    write_image(
        &reconstructed_secret_from_3_shares,
        Path::new("recontructed_secret_from_3_shares.bmp"),
    );

    let reconstructed_secret_from_all_shares = vss.reconstruct(&shares);
    write_image(
        &reconstructed_secret_from_all_shares,
        Path::new("recontructed_secret_from_all_shares.bmp"),
    );
}

おわりに

この記事では、Rust による視覚復号型秘密分散法の実装をしました。
$(2, 2)$ の方でも試してみたり、色々な画像で試したりしてみると、面白いかもしれません。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

視覚復号型秘密分散法 実装編