【 LOJ 】 \ # 6392. 「 THUPC 2018 」 암호학 제3 차 숙제 / Rsa - EXGCD

제목
1977 년 에 로 나 드 리 베 스 트 (Ron Rivest), 아 디 사 모 르 (Adi Shamir) 와 레 너 드 아 드 만 (Leonard Adleman) 은 RSA 암호 화 알고리즘 을 제시 했다.RSA 암호 화 알고리즘 은 비대 칭 암호 화 알고리즘 으로 신뢰성 은 최대 정수 분해 의 난이도 에 의 해 결정 된다.다시 말 하면 아주 큰 정수 에 대해 인수 분해 가 어 려 울 수록 RSA 알고리즘 은 믿 을 만하 다 는 것 이다.빠 른 인수 분해 알고리즘 을 찾 는 사람 이 있다 면 RSA 로 암호 화 된 정보의 신뢰성 이 극도로 떨 어 질 것 이다.
RSA 의 기본 원 리 는 다음 과 같다.
공개 키 와 비밀 키 의 생 성 은 무 작위 로 두 개의 서로 다른 질 수 p p 와 q 를 선택 하여 N = p 를 계산 합 니 다.×q N = p × q. 오로라 함수 성질 에 따라 r =φ(N)=φ(p)φ(q)=(p−1)(q−1) r = φ ( N ) = φ ( p ) φ (q) = (p - 1) (q - 1) r 보다 작은 정수 e 를 선택 하여 e - 8869 ° r - 8869 ° r 를 선택 하 십시오.r r 에 대한 곱셈 역 원 d, d×e≡1 (mod r) d × e ≡ 1   ( m o d   r) p p 와 q q 의 기록 을 소각 합 니 다.이때 (N, e) (N, e) 는 공개 키 이 고 (N, d) (N, d) 는 비밀 키 입 니 다.메시지 암호 화: 먼저 메시지 m 를 쌍방 이 약속 한 형식 으로 N N 보다 작고 N N 과 서로 질 적 인 정수 n 으로 바 꿔 야 합 니 다.메시지 가 너무 길 면 메 시 지 를 몇 단락 으로 나 눌 수 있 습 니 다. 이것 은 바로 우리 가 말 한 블록 암호 화 입 니 다. 그 다음 에 모든 부분 에 대해 다음 과 같은 공식 으로 암호 화 할 수 있 습 니 다. (mod N) n e ≡ c   ( m o d   N) 메시지 복호화: 키 d 를 이용 하여 복호화 cd 를 진행 합 니 다. (mod N) c d ≡ n   ( m o d   N )
현재 두 사용 자 는 우연 의 일치 로 같은 모드 N 을 가지 고 있 지만 비밀 키 는 다르다.두 사용자 의 공개 키 를 각각 e1 e 1 과 e2 e 2 로 설정 하고 이들 의 상호 품질 을 설정 합 니 다.명문 소식 은 m m 이 고, 밀 문 은 각각 c1, 1, 1, 1 이다. (mod N) c 1 ≡ m e 1   ( m o d   N ) c2≡me2 (mod N) c 2 ≡ m e 2   ( m o d   N) 현재 한 공격 자가 c1, c2, e1, e2, N c 1, c 2, e 1, e 2, N 을 압수 했 습 니 다.
해제
그러나 문 제 는 RSA 와 큰 관계 가 없다.×e1+y×e2=1 x × e 1 + y × e 2 = 1 exgcd 로 x, y 를 구하 면 mxe1 + ye2 = c1xc2y = m1 = m m x e 1 + y e 2 = c 1 x c 2 y = m 1 = m
코드

#include
#include
using namespace std;
typedef long long ll;
int T;ll k,c1,c2,e1,e2,mod,X,Y,x,y;
char ch;
inline ll rd()
{
    ll x=0;int f=1;
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

inline void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);k=x;x=y;y=k-a/b*y;
}

inline ll mul(ll a,ll b)
{
    ll ret=0;
    for(;b;b>>=1,a=(a<<1)%mod) if(b&1) ret=(ret+a)%mod;
    return ret;
}

inline ll fp(ll a,ll b)
{
    ll ret=1;
    for(;b;b>>=1,a=mul(a,a)) if(b&1) ret=mul(ret,a);
    return ret;
}

int main(){
    scanf("%d",&T);
    while(T--){
        c1=rd();c2=rd();e1=rd();e2=rd();mod=rd();
        exgcd(e1,e2,X,Y);
        if(X<0){exgcd(c1,mod,x,y);c1=(x%mod+mod)%mod;X=-X;}
        if(Y<0){exgcd(c2,mod,x,y);c2=(x%mod+mod)%mod;Y=-Y;}
        printf("%lld
",mul(fp(c1,X),fp(c2,Y)));
    }
}