What is or isn't illegal depends on where you live. Where I live, using any kind of digital secret to do something you shouldn't be doing is technically illegal. Guessing admin/admin or guest/guest is illegal, even if they're public knowledge, as long as you could reasonably know you're not supposed to log in.
Generally, law enforcement and judges don't blame you as long as you use best practices, but you need to adhere to responsible disclosure very strictly in order for this not to be something the police might take an interest in.
Demonstrating the insecurity of a 512 bit key is easy to do without cracking a real life key someone else owns; just generate your own to show it can be done, then use that as proof when reporting these issues to other companies. The best legal method may be to only start cracking real keys if they ignore you or deny the vulnerability, or simply report on the fact you can do it and that the company/companies you've reached out to deny the security risk.
Companies that pay for disclosure won't get you into trouble either way, but companies that are run by incompetent people will panic and turn to law enforcement quickly. White-hat hackers get sued and arrested all the time. You may be able to prove you're right in the court room, but at that point you've already spent a ton of money on lawyers and court fees.
In this case, the risk is increased by not only cracking the key (which can be argued is enough proof already, just send them their own private key as proof), but also using it to impersonate them to several mail providers to check which ones accept the cracked key. That last step could've easily been done by using one's own domains, and with impersonation being a last resort to prove an issue is valid if the company you're reporting the issue to denies the risk.