題目描述

C++中數(shù)據(jù)的類型與長(zhǎng)度參考：(這里沒顯示，大概告訴你64位機(jī)器longlong8字節(jié)）

因此，C++最大能支持的十進(jìn)制是19位的整數(shù)。如果要支持更大的整數(shù)，需要實(shí)現(xiàn)Big Number類。RSA目前比較安全的密鑰長(zhǎng)度是2048位二進(jìn)制，即是617位的十進(jìn)制。因此，C++自帶的數(shù)據(jù)類型無法實(shí)現(xiàn)安全的RSA密鑰加解密。

為了降低難度，該題不要求實(shí)現(xiàn)大數(shù)支持，因此只使用C++自帶的long long 數(shù)據(jù)類型。

該實(shí)驗(yàn)主要包含三部分：1. 公私鑰的生成。
在公私鑰生成中，有p、q、e三個(gè)參數(shù)是隨機(jī)選擇的，其中p、q要求是質(zhì)數(shù)，因此需要實(shí)現(xiàn)一個(gè)函數(shù)檢查一個(gè)整數(shù)是否是質(zhì)數(shù)。
由p、q的乘積可以得到n：n=p*q，以及n的歐拉函數(shù): φ(n) = (p-1)*(q-1)。

公鑰為（n, e）,私鑰為（n,d）

檢查一個(gè)整數(shù)是否為質(zhì)數(shù)-Rabin-Miller算法，請(qǐng)參考：https://blog.csdn.net/ECNU_LZJ/article/details/72675595或https://www.cnblogs.com/zwfymqz/p/8150969.html或https://www.cnblogs.com/zwfymqz/p/8150861.html

擴(kuò)展歐幾里得算法：請(qǐng)參考：https://blog.csdn.net/u014117943/article/details/108428551

2. 加密過程，使用加密算法c = m^e mod n，計(jì)算出密文c；

3.解密過程，使用私鑰d和解密算法m = c^d mod n, ，計(jì)算m；

加密和解密過程需要做冪運(yùn)算取余，如果直接先做冪運(yùn)算再取余，則很容易出現(xiàn)溢出，因此，我們需要采用快速冪運(yùn)算取余算法，請(qǐng)參考：https://jlice.top/p/7tbs7/

因此，該次實(shí)驗(yàn)主要難點(diǎn)在于以下三個(gè)算法的理解與實(shí)現(xiàn)：

1. Rabin-Miller算法

2. 擴(kuò)展歐幾里得算法

3. 快速冪取余算法

根據(jù)前面的算法，我們知道明文和密文都不能大于n，假設(shè)n的長(zhǎng)度為L(zhǎng)，對(duì)于明文，我們需要按照L-1的長(zhǎng)度對(duì)其分組然后再加密，每組的密文長(zhǎng)度L。解密的時(shí)候使用L的長(zhǎng)度對(duì)其進(jìn)行分組然后解密，每組的明文長(zhǎng)度為L(zhǎng)-1。分組按照整數(shù)從低到高（即從右往左）

輸入

第一行是p

第二行是q

第三行是e

第四行是待加密數(shù)據(jù)

第五行是待解密數(shù)據(jù)

輸出

第一行輸出p是否是質(zhì)數(shù)

第二行輸出q是否是質(zhì)數(shù)

第三行打印n

第四行打印d

第五行顯示輸入第四行的加密結(jié)果

第六行顯示輸入第五行的解密結(jié)果

輸入樣例1

67
43
13
281
2154

輸出樣例1

Yes
Yes
2881
853
325
54

輸入樣例2

67
43
13
54281
3252154

輸出樣例2

Yes
Yes
2881
853
21540325
281054

輸入樣例3

11
17
7
88
11

輸出樣例3

Yes
Yes
187
23
11
88

解題

題目就是一個(gè)精簡(jiǎn)的RSA算法，由于題目強(qiáng)調(diào)沒有大數(shù)，所以甚至用不到Go的math/big
最核心的三個(gè)算法在題目描述中已經(jīng)告訴我們了

1. Rabin-Miller算法，判斷一個(gè)數(shù)是否為質(zhì)數(shù)
2. 擴(kuò)展歐幾里得算法，算逆元
3. 快速冪取余算法，低于O(n)的求冪算法

其實(shí)，還有一塊我得強(qiáng)調(diào)，也是我一開始沒有看到的地方
就是題目描述最后的地方，當(dāng)待加密的內(nèi)容m與待解密的內(nèi)容c大于n時(shí)，需要分組。
可以這樣實(shí)現(xiàn)：

func buwei(num, wei int64) string {
    return fmt.Sprintf("%0*d", wei, num)
}

然后判斷一個(gè)數(shù)是否為質(zhì)數(shù)，用到的Miller-Rabin算法
沒錯(cuò)，我沒打反，因?yàn)樗徒凶鲞@個(gè)名字

func Prime(n, trials int64) bool {
    if n < 2 {
        return false
    }

    var i int64
    for ; i < trials; i++ {
        r := rand.Intn(int(n)-1) + 1
        if mrCompositeWitness(int64(r), n) {
            return false
        }
    }
    return true
}
func mrCompositeWitness(a, n int64) bool {
    theBits := bits(n - 1)
    var rem int64 = 1
    for i := len(theBits) - 1; i >= 0; i-- {
        x := rem
        rem = (rem * rem) % n

        if rem == 1 && x != 1 && x != n-1 {
            return true
        }

        if theBits[i] == 1 {
            rem = (rem * a) % n
        }

    }
    if rem != 1 {
        return true
    }
    return false
}
func bits(n int64) []int64 {
    var bits []int64
    for ; n > 0; n = n >> 1 {
        bits = append(bits, n%2)
    }
    return bits
}

求逆元的拓展歐幾里得算法，我寫在函數(shù)里

var exgcd func(a, b int64) (gcd, x, y int64)
exgcd = func(a, b int64) (gcd, x, y int64) {
        if b == 0 {
            return a, 1, 0
        }
        gcd, y, x = exgcd(b, a%b)
        y -= a / b * x
        return
    }

快速冪取模

func quic(c,d,n int64) int64 {
    var ans int64 = 1
    for d!=0 {
        if d&0x1!=0 {
            ans = (ans*c)%n
        }
        c = (c*c) %n
        d >>= 1
    }
    return ans
}

完整的代碼如下，我就不加注釋了

package main

import (
    "bufio"
    "fmt"
    "io"
    "math/rand"
    "os"
    "strconv"
)

const DefaultTrials = 6

func bits(n int64) []int64 {
    var bits []int64
    for ; n > 0; n = n >> 1 {
        bits = append(bits, n%2)
    }
    return bits
}

func mrCompositeWitness(a, n int64) bool {
    theBits := bits(n - 1)
    var rem int64 = 1
    for i := len(theBits) - 1; i >= 0; i-- {
        x := rem
        rem = (rem * rem) % n

        if rem == 1 && x != 1 && x != n-1 {
            return true
        }

        if theBits[i] == 1 {
            rem = (rem * a) % n
        }

    }
    if rem != 1 {
        return true
    }
    return false
}

func Prime(n, trials int64) bool {
    if n < 2 {
        return false
    }

    var i int64
    for ; i < trials; i++ {
        r := rand.Intn(int(n)-1) + 1
        if mrCompositeWitness(int64(r), n) {
            return false
        }
    }
    return true
}
func check(num int64) {
    if Prime(num,DefaultTrials) {
        fmt.Println("Yes")
    }else {
        fmt.Println("No")
    }
}
func qpow(a, b int64) int64 {
    var ans int64 = 1
    p := b+2
    a = (a%p + p) % p
    for ; b != 0; b >>= 1 {
        if b&1 != 0 {
            ans = (a * ans) % p
        }
        a = a * a % p
    }
    return ans
}
func buwei(num, wei int64) string {
    return fmt.Sprintf("%0*d", wei, num)
}
func make_Key(m, e, n int64) string {
    if m<n {
        return strconv.Itoa(int(quic(m,e,n)))
    }
    if m < n {
        return strconv.Itoa(int(quic(m, e, n)))
    }
    length := len(strconv.Itoa(int(n))) - 1
    var wei int64 = 1
    for i := 0; i < length; i++ {
        wei *= 10
    }
    ans := ""
    for m != 0 {
        ans = buwei(quic(m%wei, e, n), int64(length)+1) + ans
        m /= wei
    }
    return ans
}
func de_Key(c, d, n int64) string {
    if c<n {
        return strconv.Itoa(int(quic(c,d,n)))
    }
    length := len(strconv.Itoa(int(n)))

    var wei int64 = 1
    for i := 0; i < length; i++ {
        wei *= 10
    }
    ans := ""
    for c != 0 {
        ans = buwei(quic(c%wei, d, n),int64(length-1)) + ans
        c /= wei
    }
    return ans
}
func quic(c,d,n int64) int64 {
    var ans int64 = 1
    for d!=0 {
        if d&0x1!=0 {
            ans = (ans*c)%n
        }
        c = (c*c) %n
        d >>= 1
    }
    return ans
}
func id194(_r io.Reader, _w io.Writer) {
    in := bufio.NewReader(_r)
    out := bufio.NewWriter(_w)
    defer out.Flush()

    var p,q,e,m,c int64
    fmt.Fscan(in,&p,&q,&e,&m,&c)
    check(p)
    check(q)
    fmt.Println(p*q)
    fai_n := (p-1)*(q-1)
    var exgcd func(a, b int64) (gcd, x, y int64)
    exgcd = func(a, b int64) (gcd, x, y int64) {
        if b == 0 {
            return a, 1, 0
        }
        gcd, y, x = exgcd(b, a%b)
        y -= a / b * x
        return
    }
    _,d,_ := exgcd(e,fai_n)
    fmt.Println(d)
    fmt.Println(make_Key(m,e,p*q))
    fmt.Println(de_Key(c,d,p*q))
}
func main() {
    id194(os.Stdin, os.Stdout)
}