A Deterministic Complete Graph Hill Cipher with Shift128 Residual Encryption for Universal Binary Files

당신이 친구에게 비밀 메시지를 보내려고 한다고 상상해 보세요. 하지만 단순히 글자만 보내는 것이 아니라, 사진, 문서, 비디오가 가득 담긴 디지털 여행 가방 전체를 보내는 것입니다. 컴퓨터 보안의 세계에서 이것을 "암호화(encryption)"라고 부릅니다. 암호화를 당신의 여행 가방을 뒤섞어 놓아, 만약 도둑이 그것을 훔치더라도 그저 엉망진내인 무의미한 데이터로만 보이게 만드는 마법의 자물쇠라고 생각하면 됩니다. 수십 년 동안 과학자들은 이 작업을 수행하기 위해 "힐 암호(Hill Cipher)"라는 고전적인 기술을 사용해 왔습니다. 이것은 당신의 메시지를 특수한 숫자 격자(행렬)와 곱하여 엉터리 데이터로 바꾸는 거대한 수학 퍼즐처럼 작동합니다. 문제는 이 오래된 기술이 다소 까다롭다는 점입니다. 나중에 쉽게 잠금을 해제할 수 있는 적절한 숫자 격자를 찾는 것이 어렵고, 여행 가방의 크기가 정확히 맞지 않으면 매우 혼란스러워져서, 이를 맞추기 위해 종종 추가적인 "패딩(padding)" 재료를 채워 넣어야 하는 경우가 빈번합니다.

이제, 그래프 이론이라는 다른 종류의 수학을 살펴봄으로써 이 문제를 해결하기로 결심한 새로운 발명가 팀을 상상해 보세요. 그들은 단순히 무작위 숫자 격자를 추측하는 대신, "완전 그래프(complete graph)"를 사용했습니다. 완전 그래프는 마치 모든 손님이 서로 인사를 나누는 파티와 같습니다. 그들은 이 악수(handshake)의 지도가 항상 잠금을 해제할 수 있는 완벽하고 예측 가능한 격자를 만들어낸다는 사실을 깨달았습니다. 그들은 이와 함께, 메인 퍼즐에 완벽하게 들어맞지 않는 남은 데이터 조각들을 처리하기 위한 간단한 "시프트(shift)" 기술을 결합했습니다. 그 결과, 어떤 디지털 파일(PDF, 비디오, 혹은 이상한 바이너리 파일 등)이라도 크기를 변경하거나 남는 부분 없이 안전하게 잠글 수 있도록 설계된 CGHC-S128이라는 새로운 시스템이 탄생했습니다.

새로운 "파티 악수" 자물쇠

이 연구에서 Institut Teknologi Sains Bandung와 University of Jember의 연구진은 디지털 파일을 보호하는 새로운 방법인 CGHC-S128을 소개했습니다. 이것을 당신의 디지털 여행 가방을 위한 2단계 보안 시스템이라고 생각하십시오.

첫째, 그들은 "완파 그래프 힐 암호(Complete Graph Hill Cipher)"를 사용하여 파일의 주요 부분을 처리합니다. 과거에는 힐 암호 키를 만드는 것이 수천 개의 열쇠가 가득한 어두운 방에서 특정 열쇠를 찾는 것과 같았습니다. 작동하는 열쇠를 찾을 때까지 계속 시도해야 했죠. 이 새로운 방법은 더 똑똑합니다. 이 방식은 "완전 그래프(모든 사람이 서로를 아는 파티와 같은 구조)"를 사용하여 키를 생성합니다. 이러한 악수의 수학적 구조 덕분에, 연구진은 이 키가 나중에 반드시 잠금을 해제할 수 있는 형태를 갖추고 있음을 증명했습니다. 이는 마치 매번 자물쇠에 딱 맞는 마스터 키를 가진 것과 같아서, 더 이상의 추측이 필요 없습니다.

둘째, 그들은 "남은 부분"을 처리합니다. 디지털 파일은 이러한 수학적 격자에 깔끔하게 들어맞는 완벽한 크기를 갖는 경우가 드뭅니다. 보통은 간격을 채우기 위해 "패딩(padding, 추가적인 쓰레기 데이터)"을 추가해야 하며, 이는 파일 크기를 키우게 됩니다. 이 새로운 시스템은 남은 바이트를 위해 경량화된 "Shift128" 기술을 사용합니다. 만약 서랍에 딱 맞지 않는 양말 몇 켤레가 남았다면, 그것을 버리거나 상자에 쑤셔 넣는 대신, 위치를 이동시키는 특별한 옆 주머니에 밀어 넣는다고 상상해 보세요. 이를 통해 추가적인 부피를 늘리지 않고도 파일의 모든 바이트를 보호할 수 있습니다.

실험실에서의 발견

연구팀은 PDF 문서와 다양한 크기의 수학적 격자를 사용하여 새 시스템이 얼마나 잘 작동하는지 테스트했습니다. 그들은 단순히 잘 작동하기를 바란 것이 아니라, 암호화된 파일이 정말로 무작위처럼 보이는지, 그리고 나중에 완벽하게 복구될 수 있는지 확인하기 위해 수치를 직접 계산했습니다.

결과는 인상적이었습니다. 파일을 잠갔을 때, 암호화된 데이터는 거의 완벽하게 무작위처럼 보였습니다. 암호화의 세계에서 "무작위성"은 **엔트로피(entropy)**라는 점수로 측정됩니다. 완벽한 점수는 8.0입니다. 그들의 암호화된 파일은 7.999810을 기록했는데, 이는 완벽에 매우 근접한 수치입니다. 이는 암호화된 파일이 정적 노이즈(static noise)와 거의 구별되지 않을 정도로 보여서, 내부 내용을 추측하는 것이 거의 불가능함을 의미합니다.

그들은 또한 시스템이 데이터를 얼마나 잘 뒤섞는지 확인했습니다. 만약 원본 파일의 아주 작은 부분(예: 글자 하나)만 변경하더라도, 좋은 자물쇠는 전체 암호화 메시지의 약 절반을 변화시켜야 합니다. 이를 "아발란체 효과(avalanche effect)"라고 합니다. 그들의 시스템은 이상적인 50%에 거의 근접한 **49.9241%**의 아발란체 효과를 달려 달성했습니다. 이는 입력값의 아주 미세한 변화가 출력값에서 거대하고 예측 불가능한 변화를 일으킨다는 것을 시사하며, 해커들이 패턴을 찾아내는 것을 매우 어렵게 만듭니다.

또한, 시스템이 키(key)에 얼마나 민감한지도 테스트했습니다. 만약 해커가 아주 약간 잘못된 키를 사용하려고 한다면, 시스템은 완전히 다른 결과를 만들어내야 합니다. 연구진은 키를 약간만 바꿔도 출력값이 99.6114% 차이가 난다는 것을 발견했습니다. 이는 시스템이 매우 민감하며 추측 게임으로부터 매우 안전하다는 것을 의미합니다.

트레이드-오프: 속도 대 크기

보안성은 뛰어났지만, 팀은 또한 시스템의 실행 속도도 살펴보았습니다. 그들은 격자가 커지더라도 파일을 암호화(잠금)하는 과정은 매우 빠르다는 것을 발견했습니다. 그러나 복호화(잠금 해제)는 격자가 커질수록 느려졌습니다. 이는 복호화 과정에서 "행렬 역행렬(matrix inversion)"이라는 복잡한 수학 연산이 필요하기 때문인데, 이는 마치 거대한 스도쿠 퍼즐을 역순으로 푸는 것과 같습니다.

작은 격자(매개변수 n이 9에서 99 사이인 경우)의 경우, 시스템은 파일을 잠그고 푸는 데 1초도 걸리지 않을 만큼 매우 빨랐습니다. 하지만 매우 큰 격자(n = 999)를 사용했을 때는 복호화 과정이 327초(5분 이상) 넘게 걸렸습니다. 만약 더 큰 격자(n = 9999)를 사용한다면, 시스템은 멈춰버려 합리적인 시간 내에 복호화를 완료할 수 없었습니다. 이는 거대한 격자에서도 수학적으로는 완벽하게 작동하지만, 실제 환경에서는 빠른 성능을 유지하기 위해 중간 크기의 격자를 사용하는 것이 좋다는 것을 알려줍니다.

결론

연구진은 자신들의 CGHC-S128 시스템이 모든 종류의 바이너리 파일을 보호할 수 있는 견고하고 수학적으로 타당한 방법이라고 결론지었습니다. 이 시스템은 파일 크기가 정확히 유지됨을 보장하며(추가 패딩 불필요), 데이터를 무작위 노이즈처럼 완벽하게 뒤섞고, 언제나 원래의 파일로 완벽하게 복구할 수 있습니다.

그들은 PDF 파일을 잠그고, 암호화한 뒤, 다시 잠금을 해제함으로써 이를 검증했습니다. 파일은 원래의 파일과 동일한 디지털 지문(MD5 및 SHA-256 해시)을 가진 채 정확히 똑같이 복구되었습니다. 연구팀은 실질적인 사용을 위해 중간 크기의 격자를 사용하는 것이 강력한 보안과 빠른 성능 사이에서 최적의 균형을 제공한다고 제안합니다. 모든 종류의 파일을 테스트하지는 않았지만, PDF와 바이너리 데이터에 대한 테스트 결과는 이 방법이 그래프 이론의 우아함과 현대적인 파일 보호의 실용성을 결합하여 디지털 비밀을 안전하게 지키는 강력한 새로운 도구가 될 수 있음을 시사합니다.