从用C编写的无模数RSA加密中找到标志

所以我在做一个练习捕捉旗帜的问题，问题是：
I was trying to implement RSA in C but I forgot the modulus. But I think this might be good enough already?
然后是这个用C写的代码附加在问题上：

#include <stdio.h>

int main()
{
    unsigned long long int flag1 = <redacted>;
    flag1++;
    unsigned long long int flag2 = <redacted>;
    unsigned long long int ct1 = 1;
    unsigned long long int ct2 = 1;
    for (int i = 0; i<65537; i++)
    {
        ct1 = ct1 * flag1;
        ct2 = ct2 * flag2;
    }
    printf("%llu\n",ct1);
    printf("%llu\n",ct2);
}

/*OUTPUT:
7904812928421683021
16220282676865089917
*/

我想得到flag，也就是我想找到flag 1和flag 2的值，在程序中运行后输出ct 1（7904812928421683021）和ct 2（16220282676865089917），所以我想得到flag 1和flag 2的值，在程序中用“redacted”表示。
我做了一些研究，发现65537是公钥指数，也在这个问题中，它说他们忘记了模数。我已经坐在这个问题上几个小时了，仍然没有找到任何特别有用的东西。我是一个初学者在密码学，所以任何帮助将非常感谢。
如果你们中有谁能帮上忙，那就太好了。

谢谢-谢谢

从表面上看，unsigned long long int在所使用的C实现中是64位，因此以264为模执行运算。
乘以flag1或flag2 65537次的循环计算flag1 65537模264和flag2 65537模264。我们给出的结果为7904812928421683021和16220282676865089917。为了在循环之前找到flag1和flag2，我们需要计算反函数。
通过推广费马小定理，a𝜑（n）≡ 1 mod n，其中𝜑是Euler’s totient function.这意味着以𝜑（n）对模 n 取幂等于以0对模 n 取幂，这意味着模 n 取幂𝜑在指数中对模（n）起作用.换句话说，a**b ≡ a**c mod n if b ≡ c mod𝜑（n）的。
这对我们有用的方式是当我们有 a**B mod n 时，如果我们能找到一个 c 使得 bc ≡ 1 mod𝜑（n），那么我们可以计算（a**b）c mod n = a**bc mod n = a1 mod n = a mod n。
维基百科上欧拉函数的页面告诉我们𝜑（n）= n·乘积（1−1/p 对于素数 p| 因为我们的 n 是264，所以唯一能整除它的素数是2，1 −1/2 = ½，所以𝜑（264）= 264·½ = 263。
然后我们需要找到 c，使得 bc ≡ 1 mod𝜑（n），b = 65537，𝜑（n）= 263。这可以用extended Euclidean algorithm来完成。但是，由于我们只需要做一次，而且所涉及的数字足够大，在普通C实现中很难做到，我们可以简单地用ask Wolfram Alpha for 65537^-1 mod 2^64，它告诉我们9。223,090,566,172,966,913.
接下来，我们需要将一个数提升到9，223，090，566，172，966，913的幂。由于简单的迭代乘法会花费很长时间，因此我们可以使用下面的算法：

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

/*  This routine computes x**e modulo 2^64 by multiplying a running product by
    each x**p such that p is a power of two whose corresponding bit is set in
    e.  Thus, if e is 19, which is 10011 in binary, the powers of two
    represented in it are 2^16, 2^1, and 2^0, so we multiply the running
    product by x^(2^0), x^(2^1), and x^(2^16), yielding x^(2^0 + 2^1 + 2^16) =
    x^19.
*/
static uint64_t pow_u64(uint64_t x, uint64_t e)
{
    uint64_t y = 1; //  Initialize running product to 1.
    while (e)       //  Continue while bits remain in exponent.
    {
        if (e & 1)  //  If current bit is set, multiply by power of x.
            y *= x;
        x *= x;     //  Update to next x to a power-of-two.
        e >>= 1;    //  Update e to move next bit into low position.
    }
    return y;
}

static void Do(uint64_t y)
{
    uint64_t c = 9223090566172966913u;
    printf("%" PRIu64 " ^ %" PRIu64 " = %" PRIu64 ".\n", y, c, pow_u64(y, c));
}

int main(void)
{
    Do(7904812928421683021u);
    Do(16220282676865089917u);
}

这会产生输出：

7904812928421683021 ^ 9223090566172966913 = 7380380986431332173.
16220282676865089917 ^ 9223090566172966913 = 5716833052698820989.

从中我们可以看到，在循环之前，flag1和flag2的值分别为7，380，380，986，431，332，173和5，716，833，052，698，820，989。
由于flag1在被<redacted>初始化后，又被++递增，因此我们减去1得到初始值7，380，380，986，431，332，172。flag2直接被初始化为5，716，833，052，698，820，989。

从用C编写的无模数RSA加密中找到标志

1条答案

相关问题

热门标签

最新问答