샤미르의 비밀 공유(SSS, Shamir's Secret Sharing) - 구현

목차

 개요

 클래스 및 메소드 소개(중요사항만)

 코드 분석(중요사항만)

 

개요

SSS의 구현체를 분석한다. 분석 대상은 오픈 소스이다. 분석 대상 프로젝트의 링크는 다음과 같다.

https://github.com/timtiemens/secretshare

프로젝트 선정 기준은 다음과 같다.

• 개발 언어 유형 – Java

• 높은 스타 지수

• 샘플 파일 및 최소한의 문서(READEME.md)

 클래스 및 메소드 소개(중요사항만)

[SecretShare.class(중요사항만 기재)]

내부 클래스	메소드	설명	비고
PublicInfo	-	Secret Share를 생성하기 위한 공개 정보를 보관한다. 공개 정보는 아래와 같다. -       k: (t, n) 구성 요소 중 t에 해당하는 값이다. 비밀을 만들기 위한 비밀 조각들의 임계치 값(최소 개수 값) -       n: (t, n) 구성 요소 중 n에 해당하는 값이다. 생성하고자 하는 비밀 조각들의 개수이다. -       primeModulus: 비밀을 만들 때 사용하는 소수 값이다. -       Description Info: 기타 정보 모든 메소들은 유틸성이다.
SplitSecretOutput	-	split 메스도를 통해 반환되는 객체이다. 사용자는 해당 객체를 이용해서 시크릿 조각들을 사용할 수 있다.
ShareInfo	-	시크릿 조각을 갖고 있는 객체이다(x, y 값).
CombineOutput	-	시크릿 조각 조합 후의 객체
-	split	시크릿 조각들을 생성한다.
-	combine	시크릿 조각 조합(비밀 생성)

[유틸 클래스(중요사항만 기재)]

내부 클래스	메소드	설명	비고
PolyEquationImpl	-	다항 방정식을 처리하는 유틸클래스이다.
	calculateFofX	x 값을 정의하면, 해당 값으로 방정식의 계산을 실시한다. 예는 다음과 같다. fx = 1234 + 166x + 94x2   위의 값에 x가 1일 경우, 1494를 반환한다.
NumberSimplex	-	선형대수 관련 연산을 할 때 사용. 시크릿 조각을 조립할 때 사용하는 핵심 클래스
BigRational	-	큰 값의 유리수 처리
Numbermatrix	-	Number를 확장한 객체에 대해 행렬을 형성해주는 클래스

 

코드 분석(중요사항만)

[분석 대상]

- SecretShare.split 메소드

- SecretShare.combine 메소드

 

[SecretShare.split]

개요

예: PublicInfo객체의 맴버 변수를 다음과 같이 지정한다.

-       n = 16

-       k = 3

-       prime = 1613

위를 해석하면 16개의 조각을 생성하며, 3개의 조각은 임계치를 뜻한다. 즉, 3개의 조각이 존재할 경우 Secret을 생성할 수 있다. k가 3을 뜻하는 것은 이차방정식 그래프를 생성한 다는것이다. 예를 들면 아래와 같다(1234는 시크릿이다.).

 

 

코드 분석

        if (secret == null)
        {
            throw new SecretShareException("Secret cannot be null");
        }
        if (secret.signum() <= 0)
        {
            throw new SecretShareException("Secret cannot be negative");
        }
        if (publicInfo.getPrimeModulus() != null)
        {
            checkThatModulusIsAppropriate(publicInfo.getPrimeModulus(), secret);
        }

 - 유효성 검사를 실시한다.

 

BigInteger[] coeffs = new BigInteger[publicInfo.getK()];

 - k를 조회하여, k개의 계수를 생성한다 coeffs는 coefficient(계수)의 줄임말을 의미한다.

 - 계수 1개의 수준은 1개의 Array이다.

randomizeCoeffs(coeffs, random, publicInfo.getPrimeModulus(), secret);

private void randomizeCoeffs(final BigInteger[] coeffs, final Random random, final BigInteger modulus, final BigInteger secret)
    {
        for (int i = 1, n = coeffs.length; i < n; i++)
        {
            BigInteger big = null;

            //big = coeffGenOriginal(random); // see Issue#8
            big = coeffGenImproved(random, modulus);

            // FIX? TODO:? FIX?
            big = big.abs(); // make it positive

            coeffs[i] = big;

            // Book says "all coefficients are smaller than the modulus"
            if (modulus != null)
            {
                coeffs[i] = coeffs[i].mod(modulus);
            }

            // FIX? TODO: FIX? experiment says "all coefficients are smaller than the secret"
            coeffs[i] = coeffs[i].mod(secret);
        }
    }

 - Secret보다 작고, Prime보다 작은 Secret을 제외한 계수들을 생성한다.

 - 예를들면 S가 1234이고 k가 3일 때 S를 제외한 1차항, 2차항에 대해 랜덤 계수를 생성한다.

 - 0차항의 자리는 S 1234 값이 들어간다.

 

coeffs[0] = secret;

 - 0차 항은 S 값이다.

 

        SplitSecretOutput ret = new SplitSecretOutput(this.publicInfo, equation);

        for (int x = 1, n = publicInfo.getNforSplit() + 1; x < n; x++)
        {
            final BigInteger fofx = equation.calculateFofX(BigInteger.valueOf(x));
            BigInteger data = fofx;
            if (publicInfo.primeModulus != null)
            {
                data = data.mod(publicInfo.primeModulus);
            }
            final ShareInfo share = new ShareInfo(x, data, this.publicInfo);
            if (publicInfo.primeModulus != null)
            {
                if (data.compareTo(publicInfo.getPrimeModulus()) > 0)
                {
                    throw new RuntimeException("" + data + "\n" + publicInfo.getPrimeModulus() + "\n");
                }
            }
            ret.sharesInfo.add(share);
        }

        return ret;

 - x값은 1부터 시작하기 때문에 1부터 시작하여, n값(16) 까지 반복을 실시한다.

 - calculateFofX를 통해 방정식의 셈을 실시한다.

 - 해당 결과 값에 대해 mod를 실시한다.

 - 생성한 Secret 조각들은 ShareInfo 객체에 적재한다.

 - ShareInfo 객체는 SplitSecretOutput에 적재, 사용자는 최종적으로 SplitSecretOutput을 반환 받는다.

 - 해당 과정은 다음의 그림을 만드는 과정과 같다.

 

[SecretShare.combine]

개요

ShareInfo는 다음과 같다.

-       (1, 1494)

-       (2, 329)

-       (3, 965)

위의 ShareInfo 객체는 비밀을 만들기 위해 사용되는 비밀 조각들이다. 해당 조각들을 이용하여 combine 메소드를 실행한다. 해당 메소드는 불필요한 부분이 많기 때문에 해당 부분은 전부 설명에서 제외하였다.

 

코드 분석

        CombineOutput ret = null;

        sanityCheckPublicInfos(publicInfo, usetheseshares);

        if (true)
        {
            println(" SOLVING USING THESE SHARES, mod=" + publicInfo.getPrimeModulus());
            for (ShareInfo si : usetheseshares)
            {
                println("   " + si.share);
            }
            println("end SOLVING USING THESE SHARES");
        }
        if (publicInfo.getK() > usetheseshares.size())
        {
            throw new SecretShareException("Must have " + publicInfo.getK() +
                                           " shares to solve.  Only provided " +
                                           usetheseshares.size());
        }

        checkForDuplicatesOrThrow(usetheseshares);

예외 처리

 

            BigInteger[][] matrix = ele.getMatrix();
            NumberMatrix.print("SS.java", matrix, out);
            println("CVT matrix.height=" + matrix.length + " width=" + matrix[0].length);
            BigRationalMatrix brm = BigRationalMatrix.create(matrix);
            NumberMatrix.print("SS.java brm", brm.getArray(), out);

            NumberSimplex<BigRational> simplex = new NumberSimplex<BigRational>(brm, 0);
            simplex.initForSolve(out);
            simplex.solve(out);

            BigRational answer = simplex.getAnswer(1);
            if (publicInfo.getPrimeModulus() != null)
            {
                solveSecret = answer.computeBigIntegerMod(publicInfo.getPrimeModulus());
            }
            else
            {
                solveSecret = answer.bigIntegerValue();
            }

 - 제일 중요한 부분이다.

 - 역행렬 연산을 통해 선형 방정식을 계산한다.

 

 - simplex.initForSolve(out);

  -> 해당 메소드에서 역행렬을 진행하기 위한 행렬을 생성한다.

 

 - simplex.solve(out);

  -> 역행렬 작업을 진행한다.

  -> 역행렬 작업은 NumberSimplex.createAbar(E[][] array, int I, int j) 메소드에서 진행한다.

 

 - 위와 같은 선형 방정식 행렬을 역행렬 작업을 진행한다.

 - 위와 같이 3x3 행렬이 있다.

 - 역행렬 공식은 위와 같다. 위의 작업을 simplex.solve(out)에서 진행한다.

 

 - 역행렬 작업이 끝나면 위와 같이 행렬이 구성되어 있다.

 

 - 위의 행렬을 토대로 NumberSimplex.solve 메소드에서 computeAnswers 메소드를 통해 행렬 곱을 진행한다.

 

            BigRational answer = simplex.getAnswer(0);
            if (publicInfo.getPrimeModulus() != null)
            {
                solveSecret = answer.computeBigIntegerMod(publicInfo.getPrimeModulus());
            }
            else
            {
                solveSecret = answer.bigIntegerValue();
            }

 - simplex.getAnswer(0) // 리턴 씨크릿

 - modulo 1613 작업을 진행한다.