Problem Overview

The challenge provides two files: an APK and a pcapng packet capture. The solution requires analyzing network traffic and reverse engineering the encryption implementation.

Traffic Analysis

Opening the pcapng file reveals standard TCP traffic. Following TCP streams and decoding the hex content exposes the application protocol:

HELLO Adic
HELLO December
MSG Adic <cipherhex>
MSG December <cipherhex>
OK December

Two usernames are identified (December and Adic), with ciphertext located in the third parameter of each MSG packet.

APK Reverse Engineering

Using jadx to decompile the APK and searching for MSG reveals the encryption implementation:

Z z = Z.INSTANCE;
byte[] bytes = $msg.getBytes(Charsets.UTF_8);
Intrinsics.checkNotNullExpressionValue(bytes, "getBytes(...)");
String ct = z.x(bytes);
$ww.write(this$0.strToHex("MSG " + $to + " " + ct + "\n"));
$ww.flush();

The core encryption logic resides in a singleton class Z, which delegates to a native library via System.loadLibrary("u"). Extracting libu.so from the APK's lib/arm64-v8a directory and analyzing it in IDA reveals the encryption algorithm.

RSA Implementation Analysis

The native function Java_com_example_polarisctf_Z_x contains the RSA encryption routine. Reviewing the pseudo-code:

v58 = _JNIEnv::CallStaticObjectMethod(a1, v5, v11, 65537);

This confirms RSA with public exponent e = 65537. The modulus N is embedded as a 256-byte constant in the binary. Each byte must be XORed with 0xa7 to recover the actual modulus.

The recovered modulus:

N = 1359289594911861706114410263039030781889501874535854365263922081700238941971104298775704733565166223684142297360239921080802503206559783832007855750334958326368538063619171609885459927586035302195455632768752776216956554963499448005445126927786242177611054827389185330231903625073278897391670581843035646913248732183168634640757720768465749375619368398241192399373901594871829578828976563808877743744957547821735170186252185438724528024345696208656639600908162373375395068724897936084947703562847353279296559280237330305142321357271051046159817216535038453709580872952011626071015235951428711736008848437349560705229

Factoring the Modulus

The usernames (December and Adic) provide a hint: "12-Adic" suggests p-adic factorization. This leads to two primes:

p1 = 36868470706740660787721421464905401836638682160738916157575932167838186821823203816862504942939622298233577061366025690141558155900129732569808373082717267322546448162330554815263837048444519812861283264131597010739527893818171189592788916363228096169326008940877347443099182961460083037598510103570883109069
p2 = 36868618872855576637213398869023300279772349207932113322672254231788065702824758828453490531917820959873836332987860364163434774496675567525583711123546693926958840058899873462649808625168239539537851361520061079636380707986615865669345690906899493078341494168035339192519609709750087267610727174510361968641

Decryption

With p1, p2, and e = 65537, compute the private key:

from Crypto.Util.number import long_to_bytes, inverse

p1 = 36868470706740660787721421464905401836638682160738916157575932167838186821823203816862504942939622298233577061366025690141558155900129732569808373082717267322546448162330554815263837048444519812861283264131597010739527893818171189592788916363228096169326008940877347443099182961460083037598510103570883109069
p2 = 36868618872855576637213398869023300279772349207932113322672254231788065702824758828453490531917820959873836332987860364163434774496675567525583711123546693926958840058899873462649808625168239539537851361520061079636380707986615865669345690906899493078341494168035339192519609709750087267610727174510361968641
N = 1359289594911861706114410263039030781889501874535854365263922081700238941971104298775704733565166223684142297360239921080802503206559783832007855750334958326368538063619171609885459927586035302195455632768752776216956554963499448005445126927786242177611054827389185330231903625073278897391670581843035646913248732183168634640757720768465749375619368398241192399373901594871829578828976563808877743744957547821735170186252185438724528024345696208656639600908162373375395068724897936084947703562847353279296559280237330305142321357271051046159817216535038453709580872952011626071015235951428711736008848437349560705229
e = 65537

phi = (p1 - 1) * (p2 - 1)
d = inverse(e, phi)

Processing Ciphertexts

Each MSG packet contains ciphertext that must be reversed before decryption (the implementation reverses bytes during output):

ciphertexts = [
    ("December", "047a909920596822c8a618a5f2c4db7e53870013e460843f5098fc4ccf8497162ce8eee2c144ca5fb5204f8ed52a20b74706195300fac2a2fbf4e560173d94faabe8e446a43b132e003050d87f224f9b00e67341d9428d381966ca8396d473cde3363c8eeff80ce25622257e5fcde67ba4386fb6745624f5c51d574dc08c432588d4bca72918a31bb7fd0f32700923b5f9b079f3fe426b7a3ff847f337824eacab935a2d7799327166fb18469d04b78af295d11d4858c06aeaceb98be2f72649024b0eab90999a29af92a06cd53db5728898b35664b7ea61fc6ac1a8c007491e5c664d7baf3458c9fcbc28f2a979df3ee3a1f8a835214894e62b90848fe7bf07"),
    ("Adic", "bde624ad8cd6e70a55989de3dd04abacac5072a7cac00c7c9aba6b29af3340cf98ce7272433a036b40d64f7b333c98ec83174146b63872ade909e2fb7cf99d1b41d93d080166ce6d7b7f8fb2dee89f492386f3a4f7e0f4e2a3d095f8d0c4c50ec32109d2ab565f5c1343daa55c1cbf9a7e515db60359537108423eee423539e3e1b5e4dc932295a29ae20a6ca157bf506c4dbc9098cee6fe75a6a39f65364f050d59d977beb93edd1e878f213c325a065c2fca26d16453320fbe9a2a9f86c4727408d15895166c18f548c242d47dd42b5326d3b2935787ae48deebcdd4bd45e47ed26ec6a9739b7dffa3c4f8d3551d9a876540eb51c8382500fea02b76385c05"),
    # ... additional ciphertexts omitted for brevity
]


def remove_pkcs_padding(block):
    """Strip PKCS#1 v1.5 padding from decrypted message"""
    if block.startswith(b'\x02'):
        try:
            sep_index = block.index(b'\x00', 1)
            return block[sep_index+1:]
        except ValueError:
            return block
    return block


decoded_messages = []
for index, (recipient, ciphertext_hex) in enumerate(ciphertexts, 1):
    raw_bytes = bytes.fromhex(ciphertext_hex)
    reversed_bytes = raw_bytes[::-1]
    cipher_int = int.from_bytes(reversed_bytes, 'big')
    
    decrypted_int = pow(cipher_int, d, N)
    decrypted_bytes = long_to_bytes(decrypted_int)
    
    plaintext = remove_pkcs_padding(decrypted_bytes)
    message = plaintext.decode('utf-8', errors='ignore')
    
    print(f"[{index:02d}] To {recipient}:")
    print(f">>> {message}")
    print("-" * 50)
    decoded_messages.append(message)

Key Observations

1. The protocol uses a simple text-based format with hex-encoded ciphertext
2. The RSA implementation uses standard PKCS#1 v1.5 padding
3. The ciphertext requires byte-reversal before decryption due to the sender's implementation
4. The hint regarding usernames directly leads to prime factorization using p-adic methods

The challenge successfully tests multiple skills: network protocol analysis, APK reverse engineering, native library analysis, and cryptographic implementation understanding.