Patentovány jsou jen některé optimalizace na ECC, ne ECC samotné (a ano, jen v USA). Myslím, že křivka Curve25519 není patentama zatěžena vůbec.
Debian Wheezy se už konečně přestal bát ECC patentů a má ECDHE/ECDSA zapnuto v openssl. Z novějších běžných dister nemá v openssl ECC povoleny snad už jen Fedora 19 (a tudíž starší RHELy a klony).