c - Feige Fiat Shamir 计划不起作用

Question

我正在尝试在 C (Arduino) 中实现 Feige Fiat Shamir 身份识别方案 并且它有效，但仅当 e = 0 时。当 e = 1 时，它不起作用。

我怎样才能让它发挥作用？

#include <Wire.h>

int getGCD(int a, int b)
{
   int c;
   while (a != 0)
   {
      c = a;
      a = b % a;
      b = c;
   }
   return b;
}

int getCoprime(int n)
{
   int coprime;
   do
   {
      coprime = random(1, n);
   } 
   while (getGCD(n, coprime) != 1);
   return coprime;
}


//Preparation
int n = 7 * 3;
int s = getCoprime(n);
int v = (s * s) % n;

void loop ()
{
  e = random(0, 2);
  r = random(1, n);
  int y = (r * (int)pow(s, e)) % n;
  int x = (r * r) % n;

  int ysqmodn = y * y % n;
  int test = (x * (int)pow(v, e)) % n;

  if(ysqmodn == test)
  {
    Serial.print("The current ICC matches. \n");
  }  
  else
  {  
    Serial.print(String(e));
    Serial.print("\n");
  }
  delay(500);
}

Answer 1

当 e==1 时，它确实有效。当 e==0 时，计算是微不足道的，因为 s 和 v 由于 0 的幂总是 1 而掉落。这是代码仅复制和更改足以使其编译。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>

int random (int low, int high) {
    return low + rand() % (high - low);
}

int getGCD(int a, int b) {
    int c;
    while (a != 0)
    {
        c = a;
        a = b % a;
        b = c;
    }
    return b;
}

int getCoprime(int n) {
    int coprime;
    do
    {
        coprime = random(1, n);
    } 
    while (getGCD(n, coprime) != 1);
    return coprime;
}

int main(void) {
        int e, x, y, r, n, s, v, test, ysqmodn;

        srand((unsigned)time(NULL));
        n = 7 * 3;
        s = getCoprime(n);
        v = (s * s) % n;

        e = random(0, 2);
        r = random(1, n);

        printf("n=%d, s=%d, e=%d, r=%d\n", n,s,e,r);

        y = (r * (int)pow(s, e)) % n;
        x = (r * r) % n;

        ysqmodn = y * y % n;
        test = (x * (int)pow(v, e)) % n;

        if(ysqmodn == test)
            printf("The current ICC matches. \n");
        else
            printf("%d\n", e);

        return 0;
    }

示例结果:

n=21, s=2, e=1, r=2
The current ICC matches.

n=21, s=11, e=0, r=12
The current ICC matches.

n=21, s=8, e=1, r=14
The current ICC matches.

n=21, s=17, e=1, r=13
The current ICC matches.

n=21, s=1, e=0, r=9
The current ICC matches.

n=21, s=4, e=0, r=13
The current ICC matches.